In che modo questa operazione bit a bit verifica la potenza di 2?

Sto guardando un codice che dovrebbe essere banale, ma la mia matematica mi sta fallendo miseramente.

Ecco una condizione che controlla se un numero se una potenza di 2 utilizza il seguente:

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

La mia domanda è, in che modo utilizzare un AND bit a bit tra num e num – 1 determina se un numero è una potenza di 2?

Qualsiasi potere di 2 meno 1 è tutto: ( 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) 

Prendi 8 per esempio. 1000 e 0111 = 0000

Quindi quell’espressione verifica se un numero NON è un potere di 2.

Bene, il primo caso controllerà per 2 0 == 1.

Per gli altri casi, il num & (num - 1) entrano in gioco:

Questo significa che se prendi un numero qualsiasi e maschera i bit da uno in basso, otterrai uno dei due casi:

  1. se il numero è già una potenza di due, uno in meno risulterà in un numero binario che ha solo i bit di ordine inferiore impostati. Usando & non farai nulla.

    • Esempio con 8: 0100 & (0100 - 1) -> (0100 & 0011) -> 0000
  2. se il numero non è già una potenza di due, allora uno in meno non toccherà il bit più alto, quindi il risultato sarà almeno la più grande potenza di due in meno di num.

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

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

Quindi l’espressione reale trova tutto ciò che non è una potenza di due, incluso 2 0 .

Bene,

se hai X = 1000 allora x-1 = 0111. E 1000 && 0111 è 0000.

Ogni numero X che è un potere di 2 ha un x-1 che ha quelli sulla posizione x ha zero. E un bit a bit e di 0 e 1 è sempre 0.

Se il numero x non è una potenza di due, ad esempio 0110. L’x-1 è 0101 e il e dà 0100.

Per tutte le combinazioni comprese tra 0000 e 1111 questo porta 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 

E non è necessario un controllo separato per 1.

Spiegato bene qui

Anche l’espressione data considera 0 una potenza di 2. Per risolvere quell’uso !(x & (x - 1)) && x; anziché.

Determina se il numero intero è potenza di 2 o meno. Se (x & (x-1)) è zero, allora il numero è potere di 2.

Ad esempio, sia x 8 ( 1000 in binario); quindi x-1 = 7 ( 0111 ).

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

Programma C per dimostrare:

 #include  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"); } } 

Questo emette the bit is power of 2 .

 #include  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"); } } 

Questo emette the bit is not power of 2 .

Seguendo il programma in C scoprirai se il numero è potenza di 2 e trovi anche quale potenza di 2, il numero è.

 #include 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 

Ci sono altri modi per farlo: - se un numero è un potere di 2, solo 1 bit verrà impostato nel formato binario

per esempio 8 è equivalente a 0x1000, sottraendo 1 da questo, otteniamo 0x0111.

L'operazione finale con il numero originale (0x1000) indica 0.

se questo è il caso, il numero è un potere di 2

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

un altro modo può essere così:

Se prendiamo il complemento di un numero che è una potenza di 2,

per esempio complemento di 8 cioè 0x1000, otteniamo 0x0111 e ne aggiungiamo 1, otteniamo

lo stesso numero, se questo è il caso, quel numero è un potere di 2

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