Numero di bit di conteggio: come funziona questa linea? n = n &(n-1);

Question

Ho bisogno di spiegazioni su come funziona questa linea specifica.
So che questa funzione conta il numero di bit di 1, ma in che modo esattamente questa linea cancella il 1 bit più a destra?

int f(int n) { 
    int c; 
    for (c = 0; n != 0; ++c) 
     n = n & (n - 1); 
    return c; 
} 

Qualcuno può spiegarmelo brevemente o dare qualche "prova"?

Answer 1

Qualsiasi numero intero senza segno 'n' avrà le seguenti ultime cifre k: Uno seguito da (k-1) zeri: 100 ... 0 Si noti che k può essere 1 nel qual caso non ci sono zeri.

(n - 1) terminerà in questo formato: Zero seguito da (k-1) 1 di: 011 ... 1

n & (n-1) si pertanto nel zeri 'K': 100 ... 0 & 011 ... 1 = 000 ... 0

Quindi n & (n - 1) eliminerà il "1" più a destra. Ogni iterazione di questo rimuoverà sostanzialmente la cifra "1" più a destra e quindi potrai contare il numero di 1.

Answer 2

Sono stato a ripulire la manipolazione bit e mi sono imbattuto in questo. Potrebbe non essere utile al poster originale ora (3 anni dopo), ma risponderò comunque per migliorare la qualità per gli altri spettatori.

Cosa significa per n & (n-1) uguale a zero?

Dobbiamo assicurarci che lo sappiamo, poiché questo è l'unico modo per interrompere il ciclo (n != 0). Diciamo n=8. La rappresentazione bit per quello sarebbe 00001000. La rappresentazione bit per n-1 (o 7) sarebbe 00000111. L'operatore & restituisce i bit impostati in entrambi gli argomenti. Poiché 00001000 e 00000111 non hanno bit simili, il risultato sarebbe 00000000 (o zero). Potresti aver capito che il numero 8 non è stato scelto a caso. Era un esempio in cui n è la potenza di 2. Tutte le potenze di 2 (2,4,8,16, ecc.) Avranno lo stesso risultato.

Cosa succede quando si passa qualcosa che non è un esponente di 2? Ad esempio, quando n=6, la rappresentazione bit è 00000110 e n-1=5 o 00000101 .Il & viene applicata a questi 2 argomenti e hanno solo un singolo bit in comune che è 4. Ora, n=4 che non è zero così si incrementa c e cercare lo stesso processo con n=4. Come abbiamo visto sopra, 4 è un esponente di 2 quindi interromperà il ciclo nel prossimo confronto. Si sta tagliando fuori il bit più a destra fino a quando n è pari ad una potenza di 2.

Che cosa è c?

Si incrementando solo da uno ogni ciclo e inizia da 0. c è il numero di bit tagliate prima che il numero è uguale a una potenza di 2.