Cuando programamos cualquier tipo de aplicación, es común la necesidad de almacenar estados o valores de tipo boleano para nuestras estructuras de datos. Si por ejemplo programamos en C99 podemos hacer uso del tipo _Bool que ocupa un byte de longitud, también ocupa un byte el tipo bool de C++.

Sin embargo, utilizar un byte para un valor que puede ser representado por un único bit es un gasto del 88% más de recursos de los estríctamente necesarios si partimos de la base de que un byte puede almacenar ocho bits y representar 256 valores diferentes.

Si en nuestra aplicación necesitamos guardar estados o flags sobre nuestras estructuras de datos, podemos utilizar un tipo de dato para almacenar estados mucho más eficiente que un array de elementos de un byte de longitud o que propiedades de tipo booleano. Podemos usar Bitvectores.

¿Qué es un Bitvector?

Un bitvector es una variable por lo general de 16 o 32 bits (dependiendo de las necesidades de la aplicación) que sirve para almacenar estados que pueden tener solo dos posibles valores, verdadero o falso. Un entero de 32 bits está compuesto precisamente por 32 bits diferentes que pueden ser usados de forma individual para definir si el bit en una determinada posición esta activado (su valor es uno) o desactivado (su valor es cero).

Así, con tan solo cuatro bytes de memoria podemos representar 32 posibles estados diferentes que de cualquier otro modo hubieran ocupado 32 bytes (256 bits) un 400% más. Hay que tener cuidado de no confundir los Bitvectores con los bit fields de las estructuras, pues son dos conceptos totalmente diferentes.

Entrando en detalles

Un numero sin signo de 32 bits puede representar desde el número 0 al 4294967295. Cada uno de esos números puede ser representado en base dos, por lo tanto, el número 0 representa todos los bits del entero sin signo a cero y el número 4294967295 los representa a uno:

BITS : 00000000000000000000000000000000  Decimal: 0
BITS : 11111111111111111111111111111111  Decimal: 4294967295
BITS : 00000000000000001111111111111111  Decimal: 65535
BITS : 00001100001000001111000011110111  Decimal: 203485431

Una vez entendido esto, podemos ver claramente como podemos utilizar una única variable de 32 bits (un entero sin signo) donde definamos que cada posición en base dos corresponde a un estado o flag en nuestras estructuras de datos. Si todos los estados están a true la variable tendrá un valor de 4294967295 y si están a false su valor será 0.

Pero operar con bitvectores es mucho más sencillo que eso, no es necesario recordar ningún valor decimal ya que podemos utilizar los operadores a nivel de bits para hacernos la vida mucho más sencilla. Utilizando los operadores a nivel de bits, podemos crear macros o funciones que nos ayuden a fijar los valores en nuestro vector de bits.

Implementación en C

Yo siempre he sido muy amante de las macros en C, así que voy a hacer una implementación de un BitVector y de las funciones necesarias para su manipulación y uso utilizando macros. Además, el resultado es portable a cualquier plataforma y sistema operativo bien sean sus enteros de 32 o 64 bits y su ordenamiento de bits big endian o little endian.

/* 
 * 32bit bitvector defines
 */


define BV00        (1 < <  0)

define BV01        (1 <<  1)

define BV02        (1 <<  2)

define BV03        (1 <<  3)

define BV04        (1 <<  4)

define BV05        (1 <<  5)

define BV06        (1 <<  6)

define BV07        (1 <<  7)

define BV08        (1 <<  8)

define BV09        (1 <<  9)

define BV0A        (1 << 10)

define BV0B        (1 << 11)

define BV0C        (1 << 12)

define BV0D        (1 << 13)

define BV0E        (1 << 14)

define BV0F        (1 << 15)

define BV10        (1 << 16)

define BV11        (1 << 17)

define BV12        (1 << 18)

define BV13        (1 << 19)

define BV14        (1 << 20)

define BV15        (1 << 21)

define BV16        (1 << 22)

define BV17        (1 << 23)

define BV18        (1 << 24)

define BV19        (1 << 25)

define BV1A        (1 << 26)

define BV1B        (1 << 27)

define BV1C        (1 << 28)

define BV1D        (1 << 29)

define BV1E        (1 << 30)

define BV1F        (1 << 31)

/*
 * BitVector Macros
 */

define IS_SET(flag, bit)        ((flag) & (bit))

define SET_BIT(var, bit)        ((var) |= (bit))

define REMOVE_BIT(var, bit)     ((var) &= ~(bit))

define TOGGLE_BIT(var, bit)  ((var) ^= (bit))

En el ejemplo anterior hemos definido 32 posiciones de bitvector para el número entero sin signo 1. Después hemos definido unas macros con el objetivo de operar con estos bits:

• IS_SET comprueba que el bitvector flag contiene el bit encendido o no utilizando el operador bit a bit AND

• SET_BIT enciende el bit en el bitvector var utilizando el operador de asignación de bits OR

• REMOVE_BIT apaga el bit en el bitvector var utilizando el operador de asignación AND y el NOT

• TOGGLE_BIT conmuta entre encendido y apagado el bit en el bitvector var utilizando el operador de asignación XOR

¿Cómo se usa?

Vamos a ver un pequeño ejemplo de como se usaría en una aplicación:

/*
 * Bits para estados de la estructura trabajador
 */


define TRFLAG_ENFERMO     BV00

define TRFLAG_AUSENTE     BV01

define TRFLAG_TEMPORAL    BV02

define TRFLAG_INDEFINIDO  BV03

define TRFLAG_DISCONTINUO BV04

define TRFLAG_JUNIOR      BV05

define TRFLAG_SENIOR      BV06

define TRFLAG_PROJECTLEAD BV07

define TRFLAG_MANAGER     BV08

define TRFLAG_COACHER     BV09

define TRFLAG_SCRUMMAST   BV0A

/*
 * Worker Data Struct
 /
struct worker_data
{
    char      name;
    char        edad;
    int          flags;
}; 
struct worker_data w_data;
w_data.name = "Perico";
w_data.edad = 26;
w_data.flags = 0; // Fijamos todos los bits a cero
SET_BIT(w_data.flags, TRFLAG_SENIOR);
SET_BIT(w_data.flags, TRFLAG_TEMPORAL);
SET_BIT(w_data.flags, TRFLAG_SCRUMMAST);
if (IS_SET(w_data.flags, TRFLAG_MANAGER) )
{
    printf("%s es un administrativo\n", w_data.name);
}
if (IS_SET(w_data.flags, TRFLAG_SCRUMMAST))
{
    printf("%s es Scrum Manager\n", w_data.name);
}
if (!IS_SET(w_data.flags, TRFLAG_INDEFINIDO))
{
    printf("%s aún no es indefinido\n", w_data.name);
}

Hemos definido varios bitvectores relacionados con los estados de un trabajador. Hemos definido una estructura muy simple y hemos creado una variable de ese nuevo tipo. Le hemos asignado un nombre, una edad y hemos fijado el vector de bits de los flags a cero. Después hemos ejecutado una serie de acciones sobre el bitvector, veamos el valor de la variable tanto en decimal como en binario conforme van añadiéndose bits encendidos al vector:

// w_data.flags = 0;
BITS : 00000000000000000000000000000000  Decimal: 0
// SET_BIT(w_data.flags, TRFLAG_SENIOR);
BITS : 00000000000000000000000001000000  Decimal: 64
// SET_BIT(w_data.flags, TRFLAG_TEMPORAL);
BITS : 00000000000000000000000001000100  Decimal: 68
// SET_BIT(w_data.flags, TRFLAG_SCRUMMAST)
BITS : 00000000000000000000000101000100  Decimal: 324

Puedes comprobar como se van encendiendo los bits correspondientes a las posiciones representadas por cada bitvector definido.

Bonus Track

Este tipo de optimización no está restringida solo al mundo de los lenguajes de tipado estático, en Python por ejemplo, también podemos hacer uso de esta optimización a nivel de bits de forma sencilla:

def IS_SET(flag, bit):
    return (flag & (1 < < bit))
def SET_BIT(var, bit):
    return (var |= (1 << bit))
def REMOVE_BIT(var, bit):
    return (var &= (1 << bit))
def TOGGLE_BIT(var, bit):
    return (var ^= (1 << bit))

El anterior código en Python tiene el mismo efecto que lo expuesto anteriormente en C.

Conclusión

No solo optimizamos el espacio que nuestras estructuras de datos ocupan en memoria, las operaciones a nivel de bits son también más rápidas. La optimización no solo es cosa de los lenguajes de tipado estático y más bajo nivel, la optimización es una cuestión de ingeniería del software y buenas prácticas, algo, que muchos profesionales y fabricantes en la industria han olvidado por completo, sobre todo, en la del videojuego.

Más Información:

• Bit Manipulation

• Conversión realizada por operadores a nivel de bit

• Python BitManipulation