2011-03-18 25 views
7

Duplicar posible:
Best algorithm to count the number of set bits in a 32-bit integer?Contar el número de bits puestos en un entero

Hola,

me encontré con esta pregunta en una entrevista. Quiero encontrar la cantidad de bits configurados en un número dado de una manera optimizada.

Ejemplo:

Si el número dado es 7 a continuación, la salida debe ser 3 (desde binario de 7 es 111 tenemos tres 1s)

Si el dado número 8 entonces la salida debe ser de 1 (puesto que binario de 8 es 1000 tenemos uno 1s)

tenemos que encontrar el número de unidades de una manera optimizada. ¿Alguna sugerencia?

+0

Pruebe la instrucción POPCNT. – mvds

+5

Mira "Conteo de bits establecidos" en [Bit Twiddling Hacks] (http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive) – Ani

+0

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

Respuesta

2

Conceptualmente esto funciona:

int numones(int input) { 
    int num = 0; 
    do { 
     num += input % 2; 
     input = input/2; 
    } while (input > 0); 
    return num; 
} 

Una forma más optimizada (de comentaristas link anteriores):

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 
} 
2

Si está utilizando GCC, utilice la función incorporada int __builtin_popcount (unsigned int x). En algunas máquinas, esto se reducirá a una sola instrucción.

+0

pero __builtin_popcount (unsigned int x) no hace esto en una sola instrucción. Ejecuta implícitamente los métodos descritos anteriormente. –

+0

@gunner A veces es una función, pero a veces lo reemplaza con una sola instrucción si el chip tiene una instrucción popcount, al menos de acuerdo con la tradición que he leído. –

7

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.

Cuestiones relacionadas