Arroje algo de luz sobre el algoritmo de recuento de población

Question

Busqué buenos métodos para hacer popcount (recuento de bits establecidos).Encontré este, aquí

http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan

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
}

Probando algunos ejemplos, es cierto que funciona.¿Qué propiedad de las operaciones/representación binaria hace que funcione?

¿Podría sugerirnos algunas lecturas adicionales sobre popcount y representación binaria?

Answer 1

Estás empezando con una inicial. v que inicialmente tiene n bits en su conjunto.

El objetivo del juego es tener 1 bit menos para contar en cada iteración del ciclo.De esa manera, podemos contar el número de iteraciones del ciclo que fueron necesarias antes de llegar al punto donde n = 0 para calcular el valor de n inicial.

Observe que, si n = 0, entonces v = 0, por lo que el ciclo se detendrá en este punto.Pero mientras v > 0, ejecutaremos el cuerpo del bucle al menos una vez.En cada iteración, terminamos con una v que tiene 1 bit menos configurado.

Este es el por qué.La primera propiedad que necesitamos es que v && v == v.Ahora v es una secuencia de bits (el número exacto de bits depende de su máquina/SO), que puede ordenar del más significativo al menos significativo.cuando disminuyes v, podemos observar lo siguiente:

1. el bit menos significativo, llámelo v[k], que se establece en 1, se establecerá en 0;
2. todos los bits más significativos que v[k] no cambia cuando disminuyes v.

Por lo tanto, AND v con su decremento preservará todos los bits más significativos, pero establecerá v[k] en 0.Y por definición, todos los bits que son menos significativos que v[k], es decir, v[k-1]...v[0], ya son 0 porque v[k] es "el bit menos significativo que es 1".Por lo tanto, después de realizar la operación AND, todos los bits menos significativos permanecerán en 0.El resultado es que v && (v - 1) contiene un bit menos establecido en 1 que v tiene.

Answer 2

Restando un 1 poco de un 0 bit convierte ese bit en un 1 y provoca un préstamo del siguiente bit a la izquierda, lo que resulta en una resta 1 ahí también.Esto continúa en cascada hacia la izquierda hasta llegar a un 1 bit, donde restar 1 de 1 es 0.En este punto la resta ha terminado.Has convertido todos los 0 en 1 hasta el primer bit establecido y convertimos ese bit de 1 a 0.

Cuando usted and los valores antes y después, el before tiene ceros a la derecha del primer bit y el after tiene un cero en ese bit.Dado que cualquier cosa con cero es cero, se mantienen todos los ceros del valor original y también se establece el bit único en cero.