Explique la lógica detrás del algoritmo de conteo de bits de Kernighan

Question

Esta pregunta sigue directamente después de leer Bits counting algorithm (Brian Kernighan) in an integer time complexity. El código Java en cuestión es

int count_set_bits(int n) { 
    int count = 0; 
    while(n != 0) { 
     n &= (n-1); 
     count++; 
    } 
} 

Quiero entender lo que está logrando n &= (n-1) aquí? He visto el mismo tipo de construcción en otro algoritmo ingenioso para detectar si un número es una potencia de 2 como:

if(n & (n-1) == 0) { 
    System.out.println("The number is a power of 2"); 
} 

Answer 1

recorrer el código en un depurador me ayudó.

Si usted comienza con

n = 1010101 & n-1=1010100 => 1010100 
n = 1010100 & n-1=1010011 => 1010000 
n = 1010000 & n-1=1001111 => 1000000 
n = 1000000 & n-1=0111111 => 0000000 

por lo que esta iteración 4 veces. Cada iteración disminuye el valor de tal manera que el bit menos significativo que se establece en 1 desaparece.

Decrementando uno voltea el bit más bajo y cada bit hasta el primero. p.ej. si tiene 1000 ... 0000 -1 = 0111 ... 1111 no importa cuántos bits tenga que voltear y se detiene allí dejando intactos otros bits. Cuando usted y esto con n el bit más bajo de configurar y sólo el bit más bajo se convierte en 0

Answer 2

resta de 1 de un número cambia todos los bits (de derecha a izquierda) hasta que el conjunto de bits más a la derecha (incluyendo el bit establecido righmost). Por lo tanto, si restamos un número por 1 y hacemos a nivel de bit & consigo mismo (n & (n-1)), desarmamos el bit más ajustado. De esta forma, podemos deshacer 1s uno por uno de derecha a izquierda en el ciclo.

El número de veces que el ciclo itera es igual al número de bits establecidos.

Fuente: Brian Kernighan's Algorithm