c++ - tipos - Número de bits establecidos en un número

tipos de variables en c++ y sus rangos

Question

A continuación, la fórmula mágica que da el número de bits establecido en un número (peso de Hamming).

/*Code to Calculate count of set bits in a number*/
int c;
int v = 7;
v = v - ((v >> 1) & 0x55555555); // reuse input as temporary
v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // temp
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count
printf(" Number of Bits is %d",c);
/*-----------------------------------*/

de: http://graphics.stanford.edu/~seander/bithacks.html

¿Puede alguien explicarme la razón detrás de esto?

Answer 1

Es realmente un código bastante inteligente, y obviamente es mucho más difícil de entender que un simple bucle ingenuo.

Para la primera línea, tomemos una cantidad de cuatro bits y llamémosla abcd . El código básicamente hace esto:

abcd - ((abcd >> 1) & 0101) = abcd - (0abc & 0101) = abcd - 0a0c

Entonces, en cada grupo de dos bits, resta el valor del bit alto. ¿Qué nos dice eso?

11 - 1 -> 10 (two bits set)
10 - 1 -> 01 (one bit set)
01 - 0 -> 01 (one bit set)
00 - 0 -> 00 (zero bits set)

Entonces, esa primera línea establece cada grupo consecutivo de dos bits al número de bits contenidos en el valor original: cuenta los bits establecidos en grupos de dos. Llame a la cantidad de cuatro bits ABCD resultante.

La siguiente línea:

(ABCD & 0011) + ((ABCD>>2) & 0011) = 00CD + (AB & 0011) = 00CD + 00AB

Por lo tanto, toma los grupos de dos bits y suma pares juntos. Ahora, cada grupo de cuatro bits contiene el número de bits establecido en los cuatro bits correspondientes de la entrada.

En la siguiente línea, v + (v >> 4) & 0xF0F0F0F (que se analiza como (v + (v >> 4)) & 0xf0f0f0f ) hace lo mismo, agregando pares de grupos de cuatro bits juntos para que cada ocho El grupo de bits (byte) contiene el recuento de bits establecido del byte de entrada correspondiente. Ahora tenemos un número como 0x0e0f0g0h .

Tenga en cuenta que al multiplicar un byte en cualquier posición por 0x01010101 se copiará ese byte hasta el byte más significativo (además de dejar algunas copias en bytes más bajos). Por ejemplo, 0x00000g00 * 0x01010101 = 0x0g0g0g00 . Entonces, al multiplicar 0x0e0f0g0h , dejaremos e+f+g+h en el byte más alto; El >>24 al final extrae ese byte y te deja con la respuesta.