¿Cómo funciona este código para contar el número de bits de 1?

Encontré el siguiente código para contar el número de 1-bits en representación binaria para un entero dado. ¿Alguien puede explicar cómo funciona? ¿Y cómo se eligen las máscaras de bits para tal tarea? Gracias.

int count_one(int x)
{
    x = (x & (0x55555555)) + ((x >> 1) & (0x55555555));
    x = (x & (0x33333333)) + ((x >> 2) & (0x33333333));
    x = (x & (0x0f0f0f0f)) + ((x >> 4) & (0x0f0f0f0f));
    x = (x & (0x00ff00ff)) + ((x >> 8) & (0x00ff00ff));
    x = (x & (0x0000ffff)) + ((x >> 16) & (0x0000ffff));
    return x;
}

Este algoritmo utiliza x como fuente de cálculo y como memoria. Primero, piensa en qué son las máscaras de bits:

0x55 = 01010101
0x33 = 00110011
0x0f = 00001111
0xff = 11111111

Vamos con un ejemplo de 8 bits: a = 01101010

a & 0x55 = 01000000; (a >> 1) & 0x55 = 00010101 

Si sumamos estos dos juntos, obtenemos el recuento de bits de cada par de dos bits. Este resultado es como mucho 0x10ya que la máscara solo tiene un bit establecido para cada adición.

Ahora, usamos el 0x33 máscara, recuerde que cada 2 bits consecutivos contienen el resultado de la primera operación. Con esta máscara, enmascaramos 4 bits consecutivos y los agregamos. Este resultado es como mucho 0x100. Esto continúa con las otras máscaras, hasta que tengamos el resultado en x.

Pruébelo en papel, será bastante claro después de unos pocos pasos.

Es un enfoque de divide y vencerás. Tenga en cuenta que la primera línea le dará la suma de los pares subsiguientes, luego la suma de los cuádruples subsiguientes,… y finalmente el número de bits.

Ejemplo (16 bits, así que considere su código sin la última línea)

1011001111000110

En la primera línea tomamos & con bits pares e impares desplazados por uno. Luego agregamos.

Para bits pares:

num:  10 11 00 11 11 00 01 10
mask: 01 01 01 01 01 01 01 01
res:  00 01 00 01 01 00 01 00

Para bits impares:

num>>1: 01 01 10 01 11 10 00 11
mask:   01 01 01 01 01 01 01 01
res:    01 01 00 01 01 00 00 01

Sumamos esos resultados y obtenemos sumas en pares posteriores

01 10 00 10 10 00 01 01

Repetimos lo mismo con las siguientes mascarillas y turnos correspondientes

2nd: 0011 0011 0011 0011
3rd: 0000 1111 0000 1111
4th: 0000 0000 1111 1111

Y obtenemos:

2nd: 0011 0010 0010 0010  // 3 set in the first four, 2 in other quadrupels
3rd: 0000 0101 0000 0100  // 5 bits set in the first eight, 4 in the rest
4th: 0000 0000 0000 1001  // 9 bits in total

Para que esto sea más fácil de explicar, supongamos que un número entero tiene 4 bits y cada bit se representa como 1,2,3,4. Para obtener el número de 1-bitsprimero puede obtener la suma de 1 y 2 y la suma de 3 y 4 y luego sumar estas sumas.

x & (0x5) eliminará 1 y 3, y x & (0xa) eliminará 2 y 4. x & (0x5) + (x & (0xa) >> 1) utilizará 1 2 bits para almacenar la suma de 1 y 2 y utilizará 3 4 bits para almacenar la suma de 3 y 4. x & (0x5) + (x & (0xa) >> 1) es igual que x & (0x5) + (x >> 1) & (0x5).

Ahora que tenemos las sumas de 1 2 y 3 4 almacenadas en x, podemos obtener el resultado después de sumarlas. Lo mismo que arriba, x & (0x3) obtendrá la suma de 3 4 y x & (0x12) obtendrá la suma de 1 2. x & (0x3) + (x & (0x12)) >> 2 obtendrá el resultado final. x & (0x3) + (x & (0x12)) >> 2 es igual que x & (0x3) + (x >> 2) & (0x3).

Para que puedas ver lo que sucede dentro. En tu caso, en la primera línea puedes obtener la suma de 1 2 y 3 4 y 5 6 y continuar. Y en la segunda línea obtienes la suma de 1 2 3 4 y 5 6 7 8 y continúa. Entonces, al hacer esto 5 veces, obtienes el número de los 32 bits.

La primera línea trata el entero como una matriz de 16 enteros de 2 bits, el resultado de la expresión es 0 si se establecieron 0 bits en el par de 2 bits, 1 si se estableció 1 bit en el par de 2 bits (01 bin o 10 bin), y 2 si se establecieron ambos bits del par de 2 bits. Esto se debe a que consideramos el menor de cada dos bits de xy el menor de cada dos bits de x desplazado a la derecha por uno; añadiéndolos juntos. Sabemos que no se producirán acarreos fuera de los pares de 2 bits porque nuestros sumandos están limitados a 0 o 1. El resultado se almacena de nuevo en x.

x = (x & (0x55555555)) + ((x >> 1) & (0x55555555));

La siguiente línea hace lo mismo, esta vez tratando cada 2 bits como un entero separado, almacenando su suma en cada 4 bits que solían ocupar los dos sumandos. Después de esta operación, el entero se convierte esencialmente en una matriz de 8 enteros de 4 bits. Antes de la operación, cada sumando es 0, 1 o 2 (decimal) porque corresponde a las cuentas de la última línea. Debido a esto, sabemos que cada suma no será mayor que 4. Dado que cada int de 4 bits tiene un valor máximo de 15 (decimal), sabemos que esto tampoco se desbordará. Como antes, el resultado se almacena de nuevo en x.

x = (x & (0x33333333)) + ((x >> 2) & (0x33333333));

Hacemos lo mismo que arriba, esta vez sumando cada par de 4 bits en cada conjunto de 8 bits.

x = (x & (0x0f0f0f0f)) + ((x >> 4) & (0x0f0f0f0f));

Luego sumamos cada par de 8 bits en cada par de 16 bits (la mitad superior e inferior de x).

x = (x & (0x00ff00ff)) + ((x >> 8) & (0x00ff00ff));

Ahora sumamos la mitad superior e inferior de xy nos quedamos con un valor de 32 bits igual al número de bits establecidos en el valor de x.

x = (x & (0x0000ffff)) + ((x >> 16) & (0x0000ffff));

La clave aquí es que cada paso hace un conteo de bits en pares en el lugar hasta que nos quedamos con el conteo total de bits en el propio entero de 32 bits.