validar una saber numeros numero net letra isnumber hay detectar como caracter cadena c# algorithm math

c# - saber - Cómo comprobar si un número es una potencia de 2



validar caracter c# (21)

Algunos sitios que documentan y explican esto y otros trucos de twinsdling son:

Y el abuelo de ellos, el libro "Hacker''s Delight" de Henry Warren, Jr .:

Como lo explica http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2 , la expresión ((x & (x - 1)) == 0) indica incorrectamente que 0 es un poder de 2. Sugiere usar:

(!(x & (x - 1)) && x)

para corregir ese problema.

Hoy necesitaba un algoritmo simple para verificar si un número es una potencia de 2.

El algoritmo debe ser:

  1. Sencillo
  2. Corregir para cualquier valor ulong .

Se me ocurrió este simple algoritmo:

private bool IsPowerOfTwo(ulong number) { if (number == 0) return false; for (ulong power = 1; power > 0; power = power << 1) { // This for loop used shifting for powers of 2, meaning // that the value will become 0 after the last shift // (from binary 1000...0000 to 0000...0000) then, the ''for'' // loop will break out. if (power == number) return true; if (power > number) return false; } return false; }

Pero luego pensé, ¿qué tal si se comprueba si log 2 x es un número exactamente redondo? Pero cuando revisé 2 ^ 63 + 1, Math.Log devolvió exactamente 63 debido al redondeo. Así que verifiqué si 2 a la potencia 63 es igual al número original, y lo es, porque el cálculo se realiza en double s y no en números exactos:

private bool IsPowerOfTwo_2(ulong number) { double log = Math.Log(number, 2); double pow = Math.Pow(2, Math.Round(log)); return pow == number; }

Esto devolvió true para el valor incorrecto dado: 9223372036854775809 .

¿Hay un algoritmo mejor?

Aquí hay otro método que he ideado, en este caso usando | en lugar de & :

bool is_power_of_2(ulong x) { if(x == (1 << (sizeof(ulong)*8 -1) ) return true; return (x > 0) && (x<<1 == (x|(x-1)) +1)); }

Aquí hay una solución simple de C++ :

bool IsPowerOfTwo( unsigned int i ) { return std::bitset<32>(i).count() == 1; }

Después de publicar la pregunta, pensé en la siguiente solución:

Necesitamos verificar si exactamente uno de los dígitos binarios es uno. Así que simplemente cambiamos el número a la derecha un dígito a la vez y devolvemos true si es igual a 1. Si en algún punto obtenemos un número impar ( (number & 1) == 1 ), sabemos que el resultado es false . Esto demostró (usando un punto de referencia) un poco más rápido que el método original para valores verdaderos (grandes) y mucho más rápido para valores falsos o pequeños.

private static bool IsPowerOfTwo(ulong number) { while (number != 0) { if (number == 1) return true; if ((number & 1) == 1) // number is an odd number and not 1 - so it''s not a power of two. return false; number = number >> 1; } return false; }

Por supuesto, la solución de Greg es mucho mejor.

El siguiente addendum a la respuesta aceptada puede ser útil para algunas personas:

Una potencia de dos, cuando se expresa en binario, siempre se verá como 1 seguida de n ceros donde n es mayor o igual a 0. Ej:

Decimal Binary 1 1 (1 followed by 0 zero) 2 10 (1 followed by 1 zero) 4 100 (1 followed by 2 zeroes) 8 1000 (1 followed by 3 zeroes) . . . . . .

y así.

Cuando restamos 1 de este tipo de números, se convierten en 0 seguidos de n unos y, nuevamente, n es igual que arriba. Ex:

Decimal Binary 1 - 1 = 0 0 (0 followed by 0 one) 2 - 1 = 1 01 (0 followed by 1 one) 4 - 1 = 3 011 (0 followed by 2 ones) 8 - 1 = 7 0111 (0 followed by 3 ones) . . . . . .

y así.

Llegando al quid

¿Qué sucede cuando hacemos un AND a nivel de bit de un número x , que es una potencia de 2 y x - 1 ?

El uno de x se alinea con el cero de x - 1 y todos los ceros de x se alinean con los de x - 1 , lo que hace que AND a nivel de bits dé como resultado 0. Y así es como tenemos la respuesta de una sola línea mencionada anteriormente siendo Correcto.

Agregando más a la belleza de la respuesta aceptada arriba -

Entonces, tenemos una propiedad a nuestra disposición ahora:

Cuando restamos 1 de cualquier número, entonces, en la representación binaria, el extremo derecho 1 se convertirá en 0 y todos los ceros antes de ese extremo derecho 1 ahora se convertirán en 1

Un uso impresionante de esta propiedad está en descubrir: ¿Cuántos 1s están presentes en la representación binaria de un número dado? El código corto y dulce para hacer eso para un entero x dado es:

byte count = 0; for ( ; x != 0; x &= (x - 1)) count++; Console.Write("Total ones in the binary representation of x = {0}", count);

Otro aspecto de los números que se puede demostrar con el concepto explicado anteriormente es "¿Se puede representar cada número positivo como la suma de potencias de 2?" .

Sí, cada número positivo puede representarse como la suma de potencias de 2. Para cualquier número, toma su representación binaria. Ej: Tomar el número 501 .

The binary of 501 is 111110101 Because 111110101 = 100000000 + 10000000 + 1000000 + 100000 + 1000 + 000 + 100 + 00 + 1 we have 501 = 256 + 128 + 64 + 32 + 16 + 0 + 4 + 0 + 1

Encuentra si el número dado es una potencia de 2.

#include <math.h> int main(void) { int n,logval,powval; printf("Enter a number to find whether it is s power of 2/n"); scanf("%d",&n); logval=log(n)/log(2); powval=pow(2,logval); if(powval==n) printf("The number is a power of 2"); else printf("The number is not a power of 2"); getch(); return 0; }

Este programa en Java devuelve "verdadero" si el número es una potencia de 2 y devuelve "falso" si no es una potencia de 2

// To check if the given number is power of 2 import java.util.Scanner; public class PowerOfTwo { int n; void solve() { while(true) { // To eleminate the odd numbers if((n%2)!= 0){ System.out.println("false"); break; } // Tracing the number back till 2 n = n/2; // 2/2 gives one so condition should be 1 if(n == 1) { System.out.println("true"); break; } } } public static void main(String[] args) { // TODO Auto-generated method stub Scanner in = new Scanner(System.in); PowerOfTwo obj = new PowerOfTwo(); obj.n = in.nextInt(); obj.solve(); } } OUTPUT : 34 false 16 true

Hay un truco simple para este problema:

bool IsPowerOfTwo(ulong x) { return (x & (x - 1)) == 0; }

Tenga en cuenta que esta función reportará true para 0 , que no es una potencia de 2 . Si quieres excluir eso, aquí tienes cómo:

bool IsPowerOfTwo(ulong x) { return (x != 0) && ((x & (x - 1)) == 0); }

Explicación

En primer lugar, el operador binario y bit a bit de la definición de MSDN:

Binary y operadores están predefinidos para los tipos integrales y bool. Para tipos integrales, y calcula el AND lógico a nivel de bits de sus operandos. Para bool operandos, & calcula el AND lógico de sus operandos; es decir, el resultado es verdadero si y solo si ambos operandos son verdaderos.

Ahora veamos cómo se desarrolla todo esto:

La función devuelve booleano (verdadero / falso) y acepta un parámetro entrante de tipo sin signo largo (x, en este caso). Por simplicidad, supongamos que alguien ha pasado el valor 4 y ha llamado a la función así:

bool b = IsPowerOfTwo(4)

Ahora reemplazamos cada aparición de x con 4:

return (4 != 0) && ((4 & (4-1)) == 0);

Bueno, ya sabemos que 4! = 0 evals a true, hasta ahora todo bien. Pero que pasa:

((4 & (4-1)) == 0)

Esto se traduce a esto, por supuesto:

((4 & 3) == 0)

Pero, ¿qué es exactamente 4&3 ?

La representación binaria de 4 es 100 y la representación binaria de 3 es 011 (recuerda que & toma la representación binaria de estos números). Entonces tenemos:

100 = 4 011 = 3

Imagine que estos valores se apilan como una adición elemental. El operador & dice que si ambos valores son iguales a 1, entonces el resultado es 1, de lo contrario es 0. Entonces 1 & 1 = 1 , 1 & 0 = 0 , 0 & 0 = 0 , y 0 & 1 = 0 . Así que hacemos las matemáticas:

100 011 ---- 000

El resultado es simplemente 0. Así que volvemos y observamos lo que nuestra declaración de devolución ahora se traduce:

return (4 != 0) && ((4 & 3) == 0);

Lo que se traduce ahora a:

return true && (0 == 0);

return true && true;

Todos sabemos que true && true es simplemente true , y esto demuestra que para nuestro ejemplo, 4 es un poder de 2.

Mejorando la respuesta de @ user134548, sin aritmética de bits:

public static bool IsPowerOfTwo(ulong n) { if (n % 2 != 0) return false; // is odd (can''t be power of 2) double exp = Math.Log(n, 2); if (exp != Math.Floor(exp)) return false; // if exp is not integer, n can''t be power return Math.Pow(2, exp) == n; }

Esto funciona bien para:

IsPowerOfTwo(9223372036854775809)

Para cualquier potencia de 2, lo siguiente también es válido.

n y (- n) == n

NOTA: falla para n = 0, así que hay que buscarlo
Por lo que esto funciona es:
-n es el complemento 2s de n. -n tendrá cada bit a la izquierda del bit del conjunto más a la derecha de n invertido en comparación con n. Para potencias de 2 solo hay un bit establecido.

Un número es una potencia de 2 si solo contiene 1 bit establecido. Podemos usar esta propiedad y la función genérica countSetBits para encontrar si un número es potencia de 2 o no.

Este es un programa de C ++:

int countSetBits(int n) { int c = 0; while(n) { c += 1; n = n & (n-1); } return c; } bool isPowerOfTwo(int n) { return (countSetBits(n)==1); } int main() { int i, val[] = {0,1,2,3,4,5,15,16,22,32,38,64,70}; for(i=0; i<sizeof(val)/sizeof(val[0]); i++) printf("Num:%d/tSet Bits:%d/t is power of two: %d/n",val[i], countSetBits(val[i]), isPowerOfTwo(val[i])); return 0; }

No necesitamos verificar explícitamente que 0 sea un Poder de 2, ya que también devuelve False para 0.

SALIDA

Num:0 Set Bits:0 is power of two: 0 Num:1 Set Bits:1 is power of two: 1 Num:2 Set Bits:1 is power of two: 1 Num:3 Set Bits:2 is power of two: 0 Num:4 Set Bits:1 is power of two: 1 Num:5 Set Bits:2 is power of two: 0 Num:15 Set Bits:4 is power of two: 0 Num:16 Set Bits:1 is power of two: 1 Num:22 Set Bits:3 is power of two: 0 Num:32 Set Bits:1 is power of two: 1 Num:38 Set Bits:3 is power of two: 0 Num:64 Set Bits:1 is power of two: 1 Num:70 Set Bits:3 is power of two: 0

return (i & -i) == i

Ejemplo

0000 0001 Yes 0001 0001 No

Algoritmo

  1. Usando una máscara de bits, divide NUM la variable en binario

  2. IF R > 0 AND L > 0: Return FALSE

  3. De lo contrario, NUM convierte en el que no es cero.

  4. IF NUM = 1: Return TRUE

  5. De lo contrario, vaya al paso 1

Complejidad

Tiempo ~ O(log(d)) donde d es el número de dígitos binarios

bool IsPowerOfTwo(int n) { if (n > 1) { while (n%2 == 0) { n >>= 1; } } return n == 1; }

Y aquí hay un algoritmo general para averiguar si un número es una potencia de otro número.

bool IsPowerOf(int n,int b) { if (n > 1) { while (n % b == 0) { n /= b; } } return n == 1; }

bool IsPowerOfTwo(ulong x) { return x > 0 && (x & (x - 1)) == 0; }

bool isPow2 = ((x & ~(x-1))==x)? !!x : 0;

bool isPowerOfTwo(int x_) { register int bitpos, bitpos2; asm ("bsrl %1,%0": "+r" (bitpos):"rm" (x_)); asm ("bsfl %1,%0": "+r" (bitpos2):"rm" (x_)); return bitpos > 0 && bitpos == bitpos2; }

int isPowerOfTwo(unsigned int x) { return ((x != 0) && ((x & (~x + 1)) == x)); }

Esto es realmente rápido. Se tarda unos 6 minutos y 43 segundos en verificar todos los 2 ^ 32 enteros.

private static bool IsPowerOfTwo(ulong x) { var l = Math.Log(x, 2); return (l == Math.Floor(l)); }

return ((x != 0) && !(x & (x - 1)));

Si x es una potencia de dos, su único bit 1 está en la posición n . Esto significa que x – 1 tiene un 0 en la posición n . Para ver por qué, recuerda cómo funciona una resta binaria. Al restar 1 de x , el préstamo se propaga hasta la posición n ; el bit n convierte en 0 y todos los bits inferiores se convierten en 1. Ahora, como x no tiene 1 bits en común con x – 1 , x & (x – 1) es 0, y !(x & (x – 1)) es verdadero.