¿Cómo este método cuenta el número de 1s en representación binaria?

Question

Duplicar posible:
n & (n-1) what does this expression do?

Considere el siguiente algoritmo:

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

    return ones; 
} 

¿Cuál es el significado de num & (num-1)? ¿Como funciona?

Answer 1

num &= num - 1; 

borra el bit menos significativo establecido en núm.

Este algoritmo cuenta los bits establecidos al eliminarlos e incrementar un contador hasta que se agoten.

Para comprender por qué borra el bit menos significativo, debe pensar en qué disminuye la reducción de los bits y, por supuesto, comprender qué hace la operación &.

Restando en binarios funciona igual que el proceso en el que todos nos enseñaron en decimal como niños. Trabaja desde la derecha (menos significativa) hasta la izquierda, simplemente restando dígitos individuales cuando es posible, y "tomando prestado" del siguiente dígito cuando sea necesario.

Al restar 1 de un número binario que termina en un conjunto de ceros, este "préstamo" y resta convierte todos los ceros en posiciones inferiores a la derecha 1 a 1 y convierte el más a la derecha 1 a cero (porque se prestó)

A continuación, aplicar el operador & deja todos los dígitos de menor cero porque son cero en num, y establece el bit menos significativo de num a cero porque es cero en num-1.

Ambas operaciones dejan los dígitos más significativos sin cambios.

Aquí hay una buena lista de bit twiddling hacks incluida esta, que se debe a Brian Kernighan.

Answer 2

Aquí hay una respuesta más detallada (¡pero no muy bien escrita!).

Hay dos casos: o bien se establece el bit menos significativo, y luego "num-1" lo establece. O no está establecido, entonces num-1 convierte todos los ceros finales en 1, y el menos significativo 1 en un 0, el resto de los bits no se cambian. Cuando "y", todos los bits inalterados son iguales, el menos significativo 1 que está anded con un 0 se convierte en un 0 y los demás bits restantes son ceros. Esto se ilustra aquí:

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

me gustaría señalar que a menudo hay una operación de montaje para contar el número de unos en un solo ciclo. La operación se llama "popcount" y, por ejemplo, en GCC, se puede acceder a través de "__builtin_popcount", ver this link para más detalles.

Answer 3

El algoritmo funciona como una bomba, moviendo los bits de manera efectiva hacia la derecha en la variable "num".La línea

num &= num - 1; 

es donde se realiza el trabajo, hay una asignación y operación booleana AND pasando al mismo tiempo. Se trata de bit aritmética.

Pom