c - son - porque no existen memorias de 3 y 5 gigas

¿Cómo funciona esta operación bit a bit para una potencia de 2?

Question

Estoy viendo un código que debería ser trivial, pero mi matemática me está fallando miserablemente aquí.

Aquí hay una condición que verifica si un número es una potencia de 2 usando lo siguiente:

if((num != 1) && (num & (num - 1))) { /* make num pow of 2 */ }

Mi pregunta es, ¿cómo el uso de un AND a nivel de bit entre num y num - 1 determina si un número es una potencia de 2?

Answer 1

Bien,

si tiene X = 1000, entonces x-1 = 0111. Y 1000 && 0111 es 0000.

Cada número X que tiene una potencia de 2 tiene una x-1 que tiene unos en la posición x tiene ceros. Y un bit a bit y de 0 y 1 siempre es 0.

Si el número x no es una potencia de dos, por ejemplo 0110. El x-1 es 0101 y el y da 0100.

Para todas las combinbaciones dentro de 0000 - 1111 esto lleva a

   X  X-1 X && X-1  
0000 1111 0000   
0001 0000 0000 
0010 0001 0000
0011 0010 0010
0100 0011 0000
0101 0100 0100
0110 0101 0100
0111 0110 0110
1000 0111 0000
1001 1000 1000
1010 1001 1000
1011 1010 1010
1100 1011 1000
1101 1100 1100
1110 1101 1100
1111 1110 1110

Y no hay necesidad de un cheque por separado para 1.

Answer 2

Bueno, el primer caso verificará 2 ⁰ == 1.

Para los demás casos, el num & (num - 1) entra en juego:

Eso significa que si tomas cualquier número y enmascaras los bits de uno inferior, obtendrás uno de dos casos:

1. si el número es una potencia de dos ya, entonces uno menos dará como resultado un número binario que solo tiene los bits de orden inferior establecidos. Usar & no hará nada.

   • Ejemplo con 8: 0100 & (0100 - 1) -> (0100 & 0011) -> 0000

2. si el número ya no es una potencia de dos, entonces uno menos no tocará el bit más alto, por lo que el resultado será al menos la mayor potencia de dos menos que num.

   • Ejemplo con 3: 0011 & (0011 - 1) -> (0011 & 0010) -> 0010

   • Ejemplo con 13: 1101 & (1101 - 1) -> (1101 & 1100) -> 1100

Entonces la expresión real encuentra todo lo que no es una potencia de dos, incluyendo 2 ⁰ .

Answer 3

Cualquier potencia de 2 menos 1 es todas las siguientes: ( 2 ^N - 1 = 111 .... b )

2 = 2^1.  2-1 = 1 (1b)
4 = 2^2.  4-1 = 3 (11b)
8 = 2^3.  8-1 = 7 (111b)

Tome 8 por ejemplo. 1000 y 0111 = 0000

Entonces esa expresión prueba si un número NO es una potencia de 2.

Answer 4

Determina si el entero es potencia de 2 o no. Si (x & (x-1)) es cero, entonces el número es potencia de 2.

Por ejemplo, deje x ser 8 ( 1000 en binario); luego x-1 = 7 ( 0111 ).

if    1000
  &   0111
---------------
      0000

Programa C para demostrar:

#include <stdio.h>

void main()
{
    int a = 8;
    if ((a&(a-1))==0)
    {
        printf("the bit is power of 2  /n");
    }
    else 
    {
        printf("the bit is not power of 2/n");
    }
}

Esto produce the bit is power of 2 .

#include <stdio.h>

void main()
{
    int a = 7;
    if ((a&(a-1))==0)
    {
        printf("the bit is power of 2  /n");
    }
    else 
    {
        printf("the bit is not power of 2/n");
    }
}

Esto produce the bit is not power of 2 .

Answer 5

El siguiente programa en C descubrirá si el número es potencia de 2 y también encontrará qué potencia de 2, el número es.

#include<stdio.h>
void main(void)
{
    unsigned int a;
    unsigned int count=0
    unsigned int check=1;
    unsigned int position=0;
    unsigned int temp;
    //get value of a
    for(i=0;i<sizeof(int)*8;i++)//no of bits depend on size of integer on that machine
    {
        temp = a&(check << i);
        if(temp)
        {
            position = i;
            count++;
        }
    }
    if(count == 1)
    {
        printf("%d is 2 to the power of %d",a,position);
    }
    else
    {
        printf("Not a power of 2");
    }
}

Hay otras maneras de hacerlo: - si un número es una potencia de 2, solo se establecerá 1 bit en el formato binario

por ejemplo 8 es equivalente a 0x1000, restando 1 de esto, obtenemos 0x0111.

La operación final con el número original (0x1000) da 0.

si ese es el caso, el número es un poder de 2

    void IsPowerof2(int i)
    {
    if(!((i-1)&1))
    {
    printf("%d" is a power of 2, i);
    }
    }

Otra forma puede ser así:

Si tomamos el complemento de un número que es un poder de 2,

por ejemplo, complemento de 8, es decir, 0x1000, obtenemos 0x0111 y le agregamos 1, obtenemos

el mismo número, si ese es el caso, ese número es un poder de 2

    void IsPowerof2(int i)
    {
    if(((~1+1)&i) == 1)
    {
    printf("%d" is a power of 2,i):
    }
    }                                                     

Answer 6

Explicado here muy bien

También la expresión dada considera que 0 es una potencia de 2. ¡Para arreglar ese uso !(x & (x - 1)) && x; en lugar.