Tabs

lunes, 9 de enero de 2017

Contando bits

Las operaciones de cuenta de bits tienen muchas aplicaciones, como por ejemplo compresión de datos. En el ordenador todos los valores numéricos se codifican en sistema binario. Así pues, usando 32 bits de precisión el número 212 se codificaría como:

0000 0000 0000 0000 0000 0000 1101 0100

en un registro del procesador. La operación que cuenta el número de bits a 1 en un registro se conoce como bitcount() o popcount(). También se puede aplicar la definición del peso de Hamming, que es el número de elementos de una cadena distintos de 0. En el caso del ejemplo:

bitcount(212) = 4

La implementación de esta operación depende de la arquitectura de la CPU que estemos utilizando. En ocasiones, la CPU tendrá una instrucción hardware dedicada al bitcount(). Las instrucciones POPCNT y LZCNT forman parte del set ABM (Advanced Bit Manipulation). Están incluidas en la arquitectura x86 en el conjunto de instrucciones SSE 4.2.

Tener una instrucción hardware dedicada es el caso más óptimo, ya que en pocos ciclos de procesamiento tendremos nuestro resultado. Si estamos programando en un lenguaje de alto nivel debemos buscar los pasos para usar la instrucción máquina en nuestra arquitectura (normalmente llamamos a una función específica y compilamos con un flag especial).

Sin embargo existen casos en los que no disponemos de esta instrucción. En estos casos una buena solución general consiste en usar operaciones bit a bit (esta entrada de la wikipedia es fenomenal para entenderlo y antes de seguir también deberíais dominar la representación de bits en formato hexadecimal). Si estamos trabajando con registros sin signo de 32 bits el código sería el siguiente:

inline uint32_t popcount(uint32_t i) {
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    return (((i + (i >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
}

Este algoritmo se conoce como HAKMEM. La culpa de todo es de unos tales Beeler, Gosper and Schroppel, allá por el año 1972. Como véis la función es un poco confusa, así que podéis añadir un comentario diciendo "// Funciona" o "// Ojo con esta pomada". O podéis seguir leyendo la entrada y crujirme en los comentarios si no lo explico bien.

HAKMEM emplea una estrategia divide y vencerás para contar en paralelo. Veamos como lo hace tomando como ejemplo el número 212.


1) Desplazamos un bit a la derecha el registro inicial i >> 1:


0000 0000 0000 0000 0000 0000 1101 0100
----------------------------------------
0000 0000 0000 0000 0000 0000 0110 1010

2) Ahora aplicamos la función AND con el valor 0x55555555 ( i >> 1 ) & 0x55555555:

0000 0000 0000 0000 0000 0000 0110 1010
0101 0101 0101 0101 0101 0101 0101 0101
----------------------------------------
0000 0000 0000 0000 0000 0000 0100 0000

3) El resultado se lo restamos al valor inicial i - ( ( i >> 1 ) & 0x55555555 ):

0000 0000 0000 0000 0000 0000 1101 0100
0000 0000 0000 0000 0000 0000 0100 0000
----------------------------------------
0000 0000 0000 0000 0000 0000 1001 0100


Con estas tres operaciones iniciales lo que hemos obtenido es el número total de en cada par de bits del registro original. Si nos fijamos en los últimos 8 bits del registro original y nuestro resultado actual:

11 01  01 00
10 01  01 00


Podemos ver que el par 11 tiene 2 bits a uno (10) y que le siguen dos pares 01 con 1 bit a uno (01) y un par 00 con ningún bit a uno (00).

La siguiente operación se encarga de sumar estos valores de dos en dos, de forma que vamos a obtener el número de bits a uno en cada grupo de cuatro bits, veamos como:

4) Primero aplicamos la máscara 0x33333333 a nuestro último valor i & 0x33333333:

0000 0000 0000 0000 0000 0000 1001 0100
0011 0011 0011 0011 0011 0011 0011 0011
----------------------------------------
0000 0000 0000 0000 0000 0000 0001 0000

5) Desplazamos el último valor dos bits a la derecha y aplicamos la máscara (i >> 2) & 0x33333333:


0000 0000 0000 0000 0000 0000 1001 0100
----------------------------------------
0000 0000 0000 0000 0000 0000 0010 0101
0011 0011 0011 0011 0011 0011 0011 0011
----------------------------------------
0000 0000 0000 0000 0000 0000 0010 0001

6) Sumamos estos dos valores:

0000 0000 0000 0000 0000 0000 0001 0000
0000 0000 0000 0000 0000 0000 0010 0001
----------------------------------------
0000 0000 0000 0000 0000 0000 0011 0001

Ya tenemos el número total de unos en cada grupo de cuatro bits. Si comparamos con el valor original de los últimos 8 bits del registro:

1101 0100
0011 0001

Podemos ver que el primer grupo 1101 tiene 3 bits a uno (0011) y el segundo grupo 0100 tiene un bit a uno (0001).

El siguiente grupo de operaciones obtiene el número total de unos en cada grupo de 8 bits.

7) Sumamos i + (i >> 4):

0000 0000 0000 0000 0000 0000 0011 0001
0000 0000 0000 0000 0000 0000 0000 0011
----------------------------------------
0000 0000 0000 0000 0000 0000 0011 0100

8) Aplicamos la máscara de bits 0xF0F0F0F (i + (i >> 4)) & 0xF0F0F0F:

0000 0000 0000 0000 0000 0000 0011 0100
0000 1111 0000 1111 0000 1111 0000 1111
----------------------------------------
0000 0000 0000 0000 0000 0000 0000 0100

Si comparamos con el valor original de los últimos 8 bits (byte) del registro:

11010100

00000100


Vemos que concuerda que 11010100 contiene 4 bits (00000100).

Creo que ya os podéis hacer una idea de como funciona el algoritmo. Para nuestro ejemplo ya habríamos terminado, porque sólo usa los 8 bits menos significativos. Sin embargo, si habéis tenido la paciencia de llegar hasta aquí os vais a llevar una gran sorpresa en forma de propiedad matemática que nos permite obtener la cuenta de todo el registro de 32 bits.

Ahora mismo cada grupo de 8 bits (un byte) contiene la cuenta de bits a uno en el registro original para ese byte. Multiplicar por 0x1010101 tiene una propiedad especial, y es que si el número por el que multiplicamos tiene 4 bytes (A, B, C, D) el resultado de la multiplicación nos devolverá un resultado cuyos 4 bytes serán (A+B+C+D, B+C+D, C+D, D). Es decir, el primer byte contiene la cuenta de bits del registro de 32 bits, por lo que ahora sólo nos quedaría desplazar el contenido de este byte 24 bits a la derecha >> 24 para obtener el resultado.

Y bien, eso ha sido todo por hoy, espero que os haya gustado esta entrada tanto como me ha gustado a mi prepararla. Comentarios, sugerencias, ríos de tinta... son bienvenidos.

Algunas referencias:

Hackers delight, capítulo 5