In che modo questo metodo conta il numero di 1 nella rappresentazione binaria?

Question

Eventuali duplicati:
n & (n-1) what does this expression do?

Si consideri il seguente algoritmo:

int count(int num) 
{ 
    int ones = 0; 
    while(num) 
    { 
    ++ones; 
    num &= num - 1; 
    } 

    return ones; 
} 

Qual è il significato di num & (num-1)? Come funziona?

Answer 1

num &= num - 1; 

cancella il bit meno significativo impostato in num.

Questo algoritmo conta i bit impostati cancellandoli e incrementando un contatore finché non sono scomparsi.

Per capire perché cancella il bit meno significativo, è necessario pensare a cosa decrementare fa ai bit e, naturalmente, a capire cosa fa l'operazione &.

Sottrarre in opere binarie proprio come il processo in cui eravamo tutti educati in decimale da bambini. Si lavora da destra (meno significativo) a sinistra, semplicemente sottraendo le singole cifre quando possibile e "prendendo in prestito" dalla cifra successiva quando necessario.

Quando si sottrae 1 da un numero binario che termina in un insieme di zeri, questo "prendere in prestito" e sottrarre trasforma tutti gli zeri in posizioni inferiori rispetto all'estrema 1 su 1 all'estrema destra e trasforma l'1o a destra in uno zero (perché è stato preso in prestito).

quindi applicando l'operatore & lascia tutte le cifre minori zero perché sono zero nel num, e imposta il bit meno significativo del num a zero perché è zero nel num-1.

Entrambe queste operazioni lasciano invariate le cifre più significative.

Ecco un buon elenco di bit twiddling hacks compreso questo, che è dovuto a Brian Kernighan.

Answer 2

Ecco una risposta più dettagliata (ma non molto ben scritta!).

Esistono due casi: viene impostato il bit meno significativo, quindi "num-1" lo disattiva. Oppure non è impostato, quindi num-1 trasforma tutti gli zero finali in 1 e il minimo 1 in uno 0, il resto dei bit non viene modificato. Quando "e", tutti i bit non modificati sono uguali, il valore meno significativo 1 che è calcolato con uno 0 diventa uno 0 e gli altri bit rimanenti sono zero. Questo è illustrato qui:

num    =  1000110111[1]0000 
num - 1   =  1000110111[0]1111 
num & (num - 1) =  1000110111[0]0000 

rilevo che v'è spesso un'operazione di assemblaggio per contare il numero di quelle in un singolo ciclo. L'operazione è denominata "popcount" e, ad esempio in GCC, è possibile accedervi utilizzando "__builtin_popcount", vedere this link per i dettagli.

Answer 3

L'algoritmo funziona come pompa, spostando efficacemente i bit a destra nella variabile "num".La linea

num &= num - 1; 

è dove il lavoro è fatto, c'è un incarico e booleana AND succedendo allo stesso tempo. Si tratta di un po 'di aritmetica.

Pom