Ho trovato questo link per contare il numero di bit in una variabile . Penso che sia abbastanza bello, ma non riesco a capire perché funzioni. Qualcuno può offrire una spiegazione?
Ecco il codice
unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
v &= v - 1; // clear the least significant bit set
}
Qualsiasi aiuto è apprezzato.
L'idea è che ogni iterazione imposta il bit meno significativo che non è zero a zero e solo . Poiché ogni iterazione converte esattamente il bit da 1 a 0, ci vorranno tante iterazioni quante sono i bit non-0 per convertire tutti i bit a 0 (e quindi v == 0 e il ciclo termina).
Quindi, come funziona? Diciamo che il bit all'indice n è 1 e che i bit negli indici da 0 a n-1 sono tutti 0 (useremo little endianess - quindi index 0 è 1, index 1 è 2, index 2 è 4, l'indice 3 è 8 e così via).
v-1 sottrae dall'indice 0 - ma è 0, quindi lo converte in 1 e sottrae dall'indice 1 - ma è anche 0, quindi lo converte in 1 e sottrae dall'indice 2 - e così via finché non raggiungiamo indice n . Poiché l'indice n è 1, può sottrarre da esso e trasformarlo in 0 - e lì si ferma.
Quindi, v-1 è come v tranne che ci sono n 0 che diventa 1 e 1 che diventa 0. In v & v - 1 tutti gli altri bit rimangono così come sono, gli n zeri che sono stati girati a quelli rimangono 0 (perché 0 & 1 == 0 ), e quello 1 che è stato trasformato a 0 diventa 0 (perché 1 & 0 == 0 ). Quindi, in generale, solo un singolo bit è stato modificato nell'iterazione e questo cambiamento è stato da 1 a 0.
Sto aggiungendo questa risposta che è simile alla risposta sopra, ma è un modo leggermente diverso di guardare le cose, quindi potrebbe aiutare qualcuno.
Supponiamo di prendere il numero 1111 (in binario) e di sottrarre 1 da esso, otteniamo 1110 e amp; sottraendo 1, otteniamo 1101 e vediamo un pattern emergere, cioè per sottrarre 1 da un numero binario capovolgere tutti gli 0 a destra del bit meno significativo '1' a 1 e quindi capovolgere quel '1' per un 0 (supponendo che il bit più significativo sia il bit più a sinistra e il bit meno significativo sia il bit più a destra).
Quindi, supponiamo, abbiamo v = 14, che in binario è 1110, quindi per ottenere v-1, prima capovolgere lo zero a destra di 1 meno significativo a '1', che ci dà 1111 & quindi capovolgi la meno significativa 1 stessa a zero, dandoti 1101.
Ora sappiamo che il numero 'v' e 'v-1' conserverà tutti gli 1 alla sinistra del meno significativo 1 e il resto dei numeri otterrà '& ded' a zero quindi preservando 1 inferiore al numero di bit effettivamente impostato nel numero, cioè nel caso di 1110, v & v-1 = 1100 che ha 1 bit in meno impostato rispetto al suo predecessore. Questo processo si verifica per quanti "1" ci sono come il numero di bit impostati, il cui conteggio viene memorizzato nella variabile count.