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.
Tenga en cuenta que esto también se conoce como recuento de población o peso hamming. – delnan
por cierto, la cláusula if debería modificarse en while (num> 0) – Pompair
@Pompair: 'while (num)' es lo mismo que 'while (num! = 0)', por lo que es correcto. –