¿Cómo cuento el número de bits cero en un número entero?

Question

¿Qué debo hacer para encontrar el número de bits "cero" en C++? Supongamos que tengo un número entero;

int value = 276; 

Para el que tengo los bits 100010100, pero ¿cómo cuento los ceros?

Answer 1

La forma más ingenua más fácil es recorrer poco más de los bits y contar:

size_t num_zeroes = 0; 

for(size_t i = 0; i < CHAR_BIT * sizeof value; ++i) 
{ 
    if ((value & (1 << i)) == 0) 
    ++num_zeroes; 
} 

Hay toda número de mejor (para diferentes valores de "mejores") maneras, pero esto es muy claro, muy breve (en cuanto al código), y no requiere un montón de configuración.

Una micro-optimización que podría considerarse una mejora consiste en no calcular la máscara a prueba cada bit, en lugar cambiar el valor y siempre probar el bit más a la derecha:

for(size_t i = 0; i < CHAR_BIT * sizeof value; ++i, value >>= 1) 
{ 
    if ((value & 1) == 0) 
    ++num_zeroes; 
} 

Answer 2

Con mucho, la solución más obvia es una tabla de búsqueda.

/* Assuming CHAR_BITS == 8 */ 
int bitsPerByte[256] = { 8, 7, 7, 6, /* ... */ }; 
int bitsInByte(unsigned char c) { return bits[c]; } 

Answer 3

Hay un gran libro para este tipo de cosas: Hacker's Delight (sí, el nombre chupa: no tiene nada que ver con la seguridad, sino exclusivamente de bits haciendo girar). Proporciona varios algoritmos para contar '1' bits, el mejor también se puede encontrar here (aunque el libro tiene explicaciones que este sitio web no tiene).

Una vez que sepa el número de bits '1', restarlo al número de bits en su representación de tipo.

Answer 4

Puede hacer 32 menos the number of bits set.

Answer 5

Si utiliza GCC, puede probar las funciones incorporadas:

int __builtin_popcount (unsigned int x) 
int __builtin_ctz (unsigned int x) 
int __builtin_clz (unsigned int x) 

Ver GCC Documentation para más detalles.

Answer 6

Haga un cumplido y cuente los 1s.

count_zero_bits (x) = count_one_bits (~ x);

Implemente el código para contar los.

template< typename I > 
int count_one_bits(I i) 
{ 
    size_t numbits = 0; 
    for(; i != 0; i >>= 1) 
    { 
     numbits += i&1; 
    } 
} 

aunque existe un problema con mi función si i es un número negativo, porque >> pondrá bits 1 en el lado derecho por lo que obtendrá un bucle sin terminar. Si hay una forma de plantilla para aplicar un tipo sin firmar que sería ideal.

vez que tenga ese entonces:

template< typename I > int count_zero_bits(I i) 
{ 
    return count_one_bits(~i); 
} 

va a funcionar.

Answer 7

Kernighan way de contar bits puestos

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 
} 

se puede adaptar fácilmente para la tarea dada. Una cantidad de iteraciones aquí es igual a una cantidad de bits configurados.

También recomiendo el enlace anterior para otras formas de resolver este y otros tipos de tareas relacionadas con los bits. También hay un ejemplo de línea simple para obtener el conteo de bits implementado en macros.

Answer 8

Si quieres eficiencia, entonces hay una buena implementación en el libro "Hackers Delight"

22 instrucciones de salto libre.

unsigned int count_1bits(unsigned int x) 
{ 
    x = x - ((x >> 1) & 0x55555555); 
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333); 
    x = x + (x >> 8); 
    x = x + (x >> 16); 
    return x & 0x0000003F; 
} 

unsigned int count_0bits(unsigned int x) 
{ 
    return 32 - count_1bits(x); 
} 

Trataré de explicar cómo funciona. Es un algoritmo de dividir y vencer.

(x >> 1) & 0x55555555 

Desplaza todos los bits 1 paso hacia la derecha y toma el bit menos significativo de cada par de bits.

0x55555555 -> 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 (16x2 bit pairs) 

Así que, básicamente, tendrá la siguiente tabla de todas las permutaciones de 2 bits.

1. (00 >> 1) & 01 = 00 
2. (01 >> 1) & 01 = 00 
3. (10 >> 1) & 01 = 01 
4. (11 >> 1) & 01 = 01 

x - ((x >> 1) & 0x55555555); 

Luego, resta esto de los pares no desplazados.

1. 00 - 00 = 00 => 0 x 1 bits 
2. 01 - 00 = 01 => 1 x 1 bits 
3. 10 - 01 = 01 => 1 x 1 bits 
4. 11 - 01 = 10 => 2 x 1 bits 

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

Así que ahora han cambiado cada par de 2 bits por lo que su valor es ahora el número de bits de su pares originales 2 bits correspondientes ... y luego continuar en forma similar con grupos de 4 bits, 8 bits grupos, grupos de 16 bits y 32 bits finales.

Si desea una explicación mejor comprar el libro, hay una gran cantidad de buena explicación y discusión de algoritmos alternativos, etc ...

Answer 9

Según yo, la forma más sencilla para obtener el número de bits cero de manera positiva entero es la siguiente pieza de código.

int get_zero_bit_count(int num) 
{ 
    int cnt = 0; 

    while(num > 0) 
     { 
      int and_num = num & 1; 

      if (and_num != num) cnt++; 

      num >>= 1; 
     } 

     return cnt; 
    } 

Este código es fácil de entender y está explicado por selp. Esto funciona bien para enteros positivos.

Answer 10

Me sorprende que nadie ha mencionado éste:

int num_zero_bits = __builtin_popcount(~num); 

Esto le dará el número de bits cero en num cuando se utiliza con GCC.

Answer 11

Ampliando la respuesta de ronag, que otros usuarios han mencionado conduce a resultados erróneos (su algoritmo funciona sólo hasta un valor de x = 15), aquí es una versión actualizada del algoritmo:

uint8_t count_1bits(uint32_t x) { 
    x = x - ((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 & 0x3F; 
} 

uint8_t count_0bits(uint32_t x) { 
    return 32 - count_1bits(x); 
} 

El la explicación de la primera línea de ronag es correcta, sin embargo, las líneas restantes usan un enfoque diferente. En la primera línea, mediante el desplazamiento y la resta, cada par de 2 bits contendrá la cantidad de bits que se establecieron en ese par en el número original. El resto de las líneas doblan recursivamente esos números sumando el lsb de cada grupo de 2n bits al msb de ese par desplazado por n, de modo que el grupo de 2n bits contenga la cantidad de bits que se estableció en ese grupo en el número original:

01110110: 0111 (7 bits were set in the original number) 0110 (6 bits were set in the original number) 
-> 01110110 & 00001111 + (01110110 >> 4) & 00001111 
= 0110 + 0111 
= 1101 

el algoritmo anterior funciona para 32 bits enteros, pero se puede adaptar fácilmente cambiando las constantes a la longitud de bits correcta para que el patrón se mantiene igual (por ejemplo 0x5555 ... = 0,101. .., 0x0f0f ...= 00001111 ... etc.) y agregar/eliminar los cambios apropiados