Cómo verificar si un número es una potencia de 2

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

El algoritmo debe ser:

1. Simple
2. Correcto para cualquier ulongvalor.

Se me ocurrió este algoritmo simple:

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é hay de verificar si es un número exactamente redondo? Pero cuando verifiqué 2 ^ 63 + 1, devolví 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 sy no en números exactos:log2 xMath.Logdouble

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

Esto devuelve trueel valor incorrecto dado: 9223372036854775809.

¿Hay un mejor algoritmo?

Hay un truco simple para este problema:

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

Tenga en cuenta, esta función será informar truede 0que no es una potencia de 2. Si desea excluir eso, así es como:

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:

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

Ahora echemos un vistazo a cómo se desarrolla todo esto:

La función devuelve boolean (verdadero / falso) y acepta un parámetro entrante de tipo unsigned long (x, en este caso). Por simplicidad, supongamos que alguien ha pasado el valor 4 y llamó 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 verdadero, hasta ahora todo bien. Pero que pasa:

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

Esto se traduce en esto, por supuesto:

((4 & 3) == 0)

Pero que es exactamente 4&3 ?

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

100 = 4
011 = 3

Imagine que estos valores se acumulan de manera muy similar a la suma elemental. El &operador dice que si ambos valores son iguales a 1, entonces el resultado es 1, de lo contrario es 0. Por lo tanto 1 & 1 = 1, 1 & 0 = 0, 0 & 0 = 0, y 0 & 1 = 0. Entonces hacemos los cálculos:

100
011
----
000

El resultado es simplemente 0. Entonces volvemos y miramos lo que nuestra declaración de devolución ahora se traduce a:

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

Lo que se traduce ahora en:

return true && (0 == 0);

return true && true;

Todos sabemos que true && truees simple true, y esto muestra que, para nuestro ejemplo, 4 es una potencia de 2.

Algunos sitios que documentan y explican este y otros trucos poco retorcidos son:

• http://graphics.stanford.edu/~seander/bithacks.html
  ( http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2 )
• http://bits.stephan-brumme.com/
  ( http://bits.stephan-brumme.com/isPowerOfTwo.html )

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

• http://www.hackersdelight.org/

Como explica la página de Sean Anderson , la expresión ((x & (x - 1)) == 0)indica incorrectamente que 0 es una potencia de 2. Sugiere usar:

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

para corregir ese problema

return (i & -i) == i

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

Recientemente escribí un artículo sobre esto en http://www.exploringbinary.com/ten-ways-to-check-if-an-integer-is-a-power-of-two-in-c/ . Cubre el conteo de bits, cómo usar los logaritmos correctamente, el clásico "x &&! (X & (x - 1))", y otros.

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

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

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

Una potencia de dos, cuando se expresa en binario, siempre se verá como 1 seguido de n ceros donde n es mayor o igual que 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 1de este tipo de números, se convierten en 0 seguidos de n unos y nuevamente n es igual que el anterior. 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 xse alinea con el cero de x - 1y todos los ceros de xse alinean con los de uno x - 1, lo que hace que el bit Y resulte en 0. Y así es como tenemos la respuesta de una sola línea mencionada anteriormente correcta.

Además de la belleza de la respuesta aceptada arriba:

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

Cuando restamos 1 de cualquier número, en la representación binaria, el 1 más a la derecha se convertirá en 0 y todos los ceros antes de ese 1 más a la derecha ahora se convertirán en 1

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

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 probar a partir del concepto explicado anteriormente es "¿Se puede representar cada número positivo como la suma de las potencias de 2?".

Sí, cada número positivo se puede representar como la suma de las potencias de 2. Para cualquier número, tome su representación binaria. Ej: tomar el número 117.

The binary representation of 117 is 1110101

Because  1110101 = 1000000 + 100000 + 10000 + 0000 + 100 + 00 + 1
we have  117     = 64      + 32     + 16    + 0    + 4   + 0  + 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. Entonces, simplemente cambiamos el número a la derecha un dígito a la vez, y trueregresamos si es igual a 1. Si en algún momento llegamos a 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.

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

Y aquí hay un algoritmo general para descubrir 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 isPow2 = ((x & ~(x-1))==x)? !!x : 0;

Averigua 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;
}

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 necesitan aproximadamente 6 minutos y 43 segundos para verificar los 2 ^ 32 enteros.

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

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

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

Este es un programa 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 una Potencia 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

Aquí hay otro método que ideé, 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));
}

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

n & (- n) == n

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

Ejemplo

0000 0001    Yes
0001 0001    No

Algoritmo

1. Usando una máscara de bits, divida NUMla variable en binario

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

3. De lo contrario, se NUMconvierte 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 des el número de dígitos binarios

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

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)

Mark gravell sugirió esto si tiene .NET Core 3, System.Runtime.Intrinsics.X86.Popcnt.PopCount

public bool IsPowerOfTwo(uint i)
{
    return Popcnt.PopCount(i) == 1
}

Instrucción individual, más rápida que (x != 0) && ((x & (x - 1)) == 0)pero menos portátil.

En C, probé el i && !(i & (i - 1)truco y lo comparé con__builtin_popcount(i) comparé con gcc en Linux, con el indicador -mpopcnt para asegurarme de usar la instrucción POPCNT de la CPU. Mi programa de prueba contó el número de enteros entre 0 y 2 ^ 31 que eran una potencia de dos.

Al principio pensé que i && !(i & (i - 1)era un 10% más rápido, a pesar de que verifiqué que POPCNT se usaba en el desmontaje donde usaba__builtin_popcount .

Sin embargo, me di cuenta de que había incluido una declaración if, y la predicción de bifurcación probablemente estaba mejor en la versión bit twiddling. Eliminé el if y POPCNT terminó más rápido, como se esperaba.

Resultados:

Intel (R) Core (TM) i7-4771 CPU max 3.90GHz

Timing (i & !(i & (i - 1))) trick
30

real    0m13.804s
user    0m13.799s
sys     0m0.000s

Timing POPCNT
30

real    0m11.916s
user    0m11.916s
sys     0m0.000s

Procesador AMD Ryzen Threadripper 2950X 16-Core max 3.50GHz

Timing (i && !(i & (i - 1))) trick
30

real    0m13.675s
user    0m13.673s
sys 0m0.000s

Timing POPCNT
30

real    0m13.156s
user    0m13.153s
sys 0m0.000s

Tenga en cuenta que aquí la CPU Intel parece un poco más lenta que AMD con el bit twiddling, pero tiene un POPCNT mucho más rápido; AMD POPCNT no proporciona tanto impulso.

popcnt_test.c:

#include "stdio.h"

// Count # of integers that are powers of 2 up to 2^31;
int main() {
  int n;
  for (int z = 0; z < 20; z++){
      n = 0;
      for (unsigned long i = 0; i < 1<<30; i++) {
       #ifdef USE_POPCNT
        n += (__builtin_popcount(i)==1); // Was: if (__builtin_popcount(i) == 1) n++;
       #else
        n += (i && !(i & (i - 1)));  // Was: if (i && !(i & (i - 1))) n++;
       #endif
      }
  }

  printf("%d\n", n);
  return 0;
}

Ejecutar pruebas:

gcc popcnt_test.c -O3 -o test.exe
gcc popcnt_test.c -O3 -DUSE_POPCNT -mpopcnt -o test-popcnt.exe

echo "Timing (i && !(i & (i - 1))) trick"
time ./test.exe

echo
echo "Timing POPCNT"
time ./test-opt.exe

Veo que muchas respuestas sugieren devolver n &&! (N & (n - 1)) pero, según mi experiencia, si los valores de entrada son negativos, devuelve valores falsos. Compartiré otro enfoque simple aquí, ya que sabemos que una potencia de dos números tiene solo un bit establecido, por lo que simplemente contaremos el número de bits establecidos, esto llevará tiempo O (log N).

while (n > 0) {
    int count = 0;
    n = n & (n - 1);
    count++;
}
return count == 1;

Consulte este artículo para contar no. de bits fijos

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

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