c++ - que - programa para saber si un numero es primo en java

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

Question

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 sugerirme cómo podría escribir esto? ¿Me puede decir un buen sitio web donde se puede encontrar este tipo de algoritmo?

Answer 1

¿Cuál es la forma más sencilla de comprobar 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 , entonces puede realizar lo siguiente. Omite el código directo de C / C ++ porque otros ya lo han respondido, pero lo necesita si el IMC no está disponible o no está 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 compiladores de Microsoft en Visual Studio 2015 y superiores cuando AVX2 está disponible y habilitado . Para los encabezados que necesita, consulte los archivos de encabezado para intrínsecos SIMD .

Normalmente _blsr_u64 el _blsr_u64 con un _LP64_ en caso de compilar en i686. Clang necesita una pequeña solución porque usa un símbolo intrínseco nam 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

¿Me puede decir un buen sitio web donde se puede encontrar este tipo de algoritmo?

Este sitio web a menudo se cita: here .

Answer 2

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

Answer 3

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

Answer 4

Esta no es la manera más rápida o 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 porque el binario se basa en poderes de dos. Cualquier número con un solo conjunto de bits debe tener una potencia de dos.

Answer 5

Este es el método de cambio de bit 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 (el primero se establece para obtener el resultado decimal, el segundo para obtener el conjunto entero y se compara)

Answer 6

Lo siguiente sería más rápido que la respuesta más votada debido a un cortocircuito booleano y el 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));
}

Answer 7

Los poderes 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 número entero con signo. por ejemplo, un entero con signo de 8 bits con un valor de -128 se ve así:

10000000

Entonces, después de verificar que el número sea mayor que cero, podemos usar un truco ingenioso para probar que solo se ha establecido un bit.

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

Para obtener más información sobre twiddling, mira here .

Answer 8

Otro camino a seguir (tal vez no el más rápido) es determinar si ln (x) / ln (2) es un número entero.

Answer 9

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

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

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

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.

Answer 10

para cualquier potencia de 2, lo siguiente también se cumple.

n & (- n) == n

NOTA: La condición es verdadera para n = 0, aunque no es una potencia de 2.
La razón por la cual 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 volteado en comparación con n. Para las potencias de 2 solo hay un bit establecido.

Answer 11

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

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

Answer 12

Enfoque n. ° 1:

Divida el número por 2 en forma reclusiva para verificarlo.

Complejidad del tiempo: O (log2n).

Enfoque # 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 Y a nivel de bit de ambos números es 0 0 0 0 = 0.

Complejidad del tiempo: 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 del tiempo: O (1).

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

Answer 13

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

Answer 14

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