¿Cuál es la forma más sencilla de probar si un número es una potencia de 2 en C ++?

Necesito una función como esta:

// return true iff 'n' is a power of 2, e.g.
// is_power_of_2(16) => true  is_power_of_2(3) => false
bool is_power_of_2(int n);

¿Alguien puede sugerir cómo podría escribir esto? ¿Puede decirme un buen sitio web donde se pueda encontrar este tipo de algoritmo?

(n & (n - 1)) == 0es mejor. Sin embargo, tenga en cuenta que devolverá incorrectamente verdadero para n = 0, por lo que si eso es posible, querrá verificarlo explícitamente.

http://www.graphics.stanford.edu/~seander/bithacks.html tiene una gran colección de ingeniosos algoritmos de alteración de bits, incluido este.

Una potencia de dos tendrá solo un bit establecido (para números sin signo). Algo como

bool powerOfTwo = !(x == 0) && !(x & (x - 1));

Funcionará bien; uno menor que una potencia de dos son todos 1 en los bits menos significativos, por lo que debe AND a 0 bit a bit.

Como estaba asumiendo números sin firmar, la prueba == 0 (que originalmente olvidé, lo siento) es adecuada. Es posible que desee una prueba> 0 si está utilizando enteros con signo.

Las potencias de dos en binario se ven así:

1: 0001
2: 0010
4: 0100
8: 1000

Tenga en cuenta que siempre hay exactamente 1 bit configurado. La única excepción es con un entero con signo. Por ejemplo, un entero de 8 bits con signo con un valor de -128 se ve así:

10000000

Entonces, después de verificar que el número es mayor que cero, podemos usar un pequeño truco inteligente para probar que se establece uno y solo un bit.

bool is_power_of_2(int x) {
    return x > 0 && !(x & (x−1));
}

Para más juegos, vea aquí .

Enfoque n. ° 1:

Divida el número por 2 de forma reclusa para comprobarlo.

Complejidad del tiempo: O (log2n).

Enfoque n. ° 2:

Bitwise Y el número con su número anterior debe ser igual a CERO.

Ejemplo: Número = 8 Binario de 8: 1 0 0 0 Binario de 7: 0 1 1 1 y el AND bit a bit de ambos números es 0 0 0 0 = 0.

Complejidad temporal: O (1).

Enfoque n. ° 3:

Bitwise XOR el número con su número anterior debe ser la suma de ambos números.

Ejemplo: Número = 8 Binario de 8: 1 0 0 0 Binario de 7: 0 1 1 1 y el XOR bit a bit de ambos números es 1 1 1 1 = 15.

Complejidad temporal: O (1).

http://javaexplorer03.blogspot.in/2016/01/how-to-check-number-is-power-of-two.html

bool is_power_of_2(int i) {
    if ( i <= 0 ) {
        return 0;
    }
    return ! (i & (i-1));
}

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

n & (- n) == n

NOTA: La condición es verdadera para n = 0, aunque no es una potencia de 2. La
razón por la que esto funciona es:
-n es el complemento a 2 de n. -n tendrá todos los bits 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.

En C ++ 20 hay std::ispow2algo que puede usar exactamente para este propósito si no necesita implementarlo usted mismo:

#include <bit>
static_assert(std::ispow2(16));
static_assert(!std::ispow2(15));

Este es probablemente el más rápido, si usa GCC. Solo usa una instrucción de cpu POPCNT y una comparación. La representación binaria de cualquier potencia de 2 números, siempre tiene un solo bit establecido, los demás bits son siempre cero. Entonces contamos el número de bits establecidos con POPCNT, y si es igual a 1, el número es potencia de 2. No creo que haya ningún método posible más rápido. Y es muy simple, si lo entendiste una vez:

if(1==__builtin_popcount(n))

Lo siguiente sería más rápido que la respuesta más votada debido al cortocircuito booleano y al hecho de que la comparación es lenta.

int isPowerOfTwo(unsigned int x)
{
  return x && !(x & (x – 1));
}

Si sabes que x no puede ser 0 entonces

int isPowerOfTwo(unsigned int x)
{
  return !(x & (x – 1));
}

return n > 0 && 0 == (1 << 30) % n;

¿Cuál es la forma más sencilla de probar si un número es una potencia de 2 en C ++?

Si tiene un procesador Intel moderno con las instrucciones de manipulación de bits , puede realizar lo siguiente. Omite el código C / C ++ directo porque otros ya lo han respondido, pero lo necesita si BMI no está disponible o habilitado.

bool IsPowerOf2_32(uint32_t x)
{
#if __BMI__ || ((_MSC_VER >= 1900) && defined(__AVX2__))
    return !!((x > 0) && _blsr_u32(x));
#endif
    // Fallback to C/C++ code
}

bool IsPowerOf2_64(uint64_t x)
{
#if __BMI__ || ((_MSC_VER >= 1900) && defined(__AVX2__))
    return !!((x > 0) && _blsr_u64(x));
#endif
    // Fallback to C/C++ code
}

GCC, ICC y Clang señalan el soporte de BMI con __BMI__. Está disponible en los compiladores de Microsoft en Visual Studio 2015 y versiones posteriores cuando AVX2 está disponible y habilitado . Para conocer los encabezados que necesita, consulte Archivos de encabezado para conocer los elementos intrínsecos de SIMD .

Normalmente lo guardo _blsr_u64con un _LP64_en caso de compilar en i686. Clang necesita una pequeña solución porque usa un nam de símbolo intrínseco ligeramente diferente:

#if defined(__GNUC__) && defined(__BMI__)
# if defined(__clang__)
#  ifndef _tzcnt_u32
#   define _tzcnt_u32(x) __tzcnt_u32(x)
#  endif
#  ifndef _blsr_u32
#    define  _blsr_u32(x)  __blsr_u32(x)
#  endif
#  ifdef __x86_64__
#   ifndef _tzcnt_u64
#    define _tzcnt_u64(x) __tzcnt_u64(x)
#   endif
#   ifndef _blsr_u64
#     define  _blsr_u64(x)  __blsr_u64(x)
#   endif
#  endif  // x86_64
# endif  // Clang
#endif  // GNUC and BMI

¿Puede decirme un buen sitio web donde se pueda encontrar este tipo de algoritmo?

Este sitio web se cita a menudo: Bit Twiddling Hacks .

Esta no es la forma más rápida ni la más corta, pero creo que es muy legible. Entonces haría algo como esto:

bool is_power_of_2(int n)
  int bitCounter=0;
  while(n) {
    if ((n & 1) == 1) {
      ++bitCounter;
    }
    n >>= 1;
  }
  return (bitCounter == 1);
}

Esto funciona ya que el binario se basa en potencias de dos. Cualquier número con un solo bit establecido debe ser una potencia de dos.

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

bool is_power_of_2(int x) {
    return x > 0 && (x<<1 == (x|(x-1)) +1));
}

Es posible a través de c ++

int IsPowOf2(int z) {
double x=log2(z);
int y=x;
if (x==(double)y)
return 1;
else
return 0;
}

Sé que esta es una publicación muy antigua, pero pensé que podría ser interesante publicarla aquí.

De Code-Golf SE (así que todo el crédito para el (los) que escribieron esto): Showcase of Languages

(Párrafo sobre C , subpárrafo Longitud 36 fragmento )

bool isPow2(const unsigned int num){return!!num&!(num&(num-1));}

Otra forma de hacerlo (quizás no la más rápida) es determinar si ln (x) / ln (2) es un número entero.

Este es el método de cambio de bits en T-SQL (SQL Server):

SELECT CASE WHEN @X>0 AND (@X) & (@X-1)=0 THEN 1 ELSE 0 END AS IsPowerOfTwo

Es mucho más rápido que hacer un logaritmo cuatro veces (primer conjunto para obtener un resultado decimal, segundo conjunto para obtener un conjunto entero y comparar)