Warren tiene un capítulo completo sobre conteo de bits, incluido uno sobre Conting de 1 bit.
El problema se puede resolver dividiendo y conquistando, es decir, sumando 32bits se resuelve sumando 2 números de 16 bits y así sucesivamente. Esto significa que simplemente agregamos el número de unidades en dos campos de n bits juntos en un campo 2n.
Example:
10110010
01|10|00|01
0011|0001
00000100
El código de este se ve algo como esto:
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);
Estamos utilizando ((x >> 1) & 0x55555555) en lugar de (x & 0xAAAAAAAA) >> 1 sólo porque quiero evitar generar dos constantes grandes en un registro. Si lo miras, puedes ver que es el último y es bastante inútil y otros y también se pueden omitir si no hay peligro de que la suma se prolongue. Así que si se simplifica el código, nos encontramos con esto:
int pop(unsigned x) {
x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0f0f0f0f;
x = x + (x >> 8);
x = x + (x >> 16);
return x & 0x0000003f;
}
Eso sería 21 instrucciones, rama libres en una máquina RISC habitual. Dependiendo de cuántos bits se establezcan en promedio, puede ser más rápido o más lento que el kerrigan loop, aunque probablemente también dependa de la CPU utilizada.
Pruebe la instrucción POPCNT. – mvds
Mira "Conteo de bits establecidos" en [Bit Twiddling Hacks] (http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive) – Ani
Tu pregunta no está clara. ¿Qué es un "número de campo de bit"? ¿Número de 1 bits individuales? ¿O el ancho desde el primer 1 bit hasta el último 1 bit? Los ejemplos que proporcionó fueron elegidos mal. Ellos son ambiguos. Por ejemplo, ¿qué es "número de campo de bit" para 10, que es '1010' en binario? ¿Es 2 o 3? – AnT