Construcción una expresión lógica que contará bits en un byte

Question

Al entrevistar a nuevos candidatos, generalmente les pedimos que escriban un código C para contar el número de bits con valor 1 en una variable de byte dada (por ejemplo, el byte 3 tiene dos 1 bits). Conozco todas las respuestas comunes, como el desplazamiento a la derecha ocho veces o la tabla de índice constante de 256 resultados precalculados.

Pero, ¿hay una manera más inteligente sin usar la tabla precalculada? ¿Cuál es la combinación más corta de operaciones de bytes (AND, OR, XOR, +, -, negación binaria, desplazamiento a la izquierda y derecha) que calcula el número de 1 bits?

Answer 1

Hay al menos dos soluciones más rápidas, con diferentes características de rendimiento:

1. resta uno y Y los nuevos y antiguos valores. Repita hasta cero. Cuenta el número de iteraciones. Complejidad: O (B), donde B es el número de un bit.

   int bits(unsigned n) 
   { 
       for (int i = 0; n; ++i) 
       { 
        n &= n - 1; 
       } 
       return i; 
   } 
   

2. Añadir pares de bits a continuación, grupos de cuatro, a continuación, grupos de ocho, hasta llegar al tamaño de la palabra. Hay un truco que le permite agregar todos los grupos en cada nivel en una sola pasada. Complejidad: O (log (N)), donde N es el número total de bits.

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

   Esta versión es un poco ingenua. Si lo piensas un poco, puedes evitar algunas de las operaciones.

Answer 2

Aquí está una lista de formas Bit twiddling hacks

Answer 3

Java lo hace de esta manera (usando números enteros de 32 bits) (14 cálculos)

public static int bitCount(int i) { 
    // HD, Figure 5-2 
    i = i - ((i >>> 1) & 0x55555555); 
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); 
    i = (i + (i >>> 4)) & 0x0f0f0f0f; 
    i = i + (i >>> 8); 
    i = i + (i >>> 16); 
    return i & 0x3f; 
} 

Para enteros de 16 bits (corto), el método puede ser reescrita para:

private static int bitCount(int i) { 
    // HD, Figure 5-2 
    i = i - ((i >>> 1) & 0x5555); 
    i = (i & 0x3333) + ((i >>> 2) & 0x3333); 
    i = (i + (i >>> 4)) & 0x0f0f; 
    i = i + (i >>> 4); 
    i = i + (i >>> 8); 
    return i & 0x3f; 
} 

para enteros de 8 bits (byte), que es un poco más complicado, pero la ge la idea neral está ahí.

Se puede extraer de este enlace para obtener más información sobre las funciones de conteo de bits rápido: http://gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/

La forma más rápida/más fácil para cualquier número entero, que es O (0) para el mejor de los casos y O (n) para el peor de los casos (donde n es el número de bits en el valor) es

static private int bitcount(int n) { 
    int count = 0 ; 
    while (n != 0) { 
     count++ ; 
     n &= (n - 1) ; 
    } 
    return count ; 
}