Aunque haya pasado mucho tiempo desde tu último código en ensamblador, con cierta frecuencia uno se acuerda de las máscaras de bits. Las operaciones que sobre ellas se realizan son tremendamente rápidas, de hecho, este tipo de operaciones están (literalmente) escritas a fuego en la piel del procesador (bueno, quizás quede algún reducto a las microprogramadas).
A más alto nivel, ya ni para las enumeraciones nos acordamos de ellas, dejamos que los compiladores hagan el trabajo.
Sin embargo, hay situaciones en alto nivel en el que la solución a un problema viene de la mano de las máscaras de bits. Si tal cosa merece tu tiempo, déjame mostrarte algunos ejemplos que hacen uso de las propiedades de los bits para resolver problemas de más “alto nivel”.
Notas sobre la implementación
Desde un punto de vista práctico, trabajar con máscaras de bits supone, o bien limitarse a tamaños de palabra fijos (8, 16, 32, 64, … bits), o bien extender el resultado a cadenas de bits, lo que generaliza la solución (muy eficiente, eso sí) a costa de quitarle la gracia de resolver el problema sin iterar.
Al fondo a la derecha
En Solveet propusieron el problema de “al fondo a la derecha”, que consiste en, dado el mapa de un establecimiento, indicar si hay o no, una ruta, desde abajo, a la casilla superior derecha.
Por ejemplo, el siguiente mapa sí tiene una ruta “al fondo a la derecha”:
Se puede implementar un algoritmo que itere revisando todos los posibles caminos tipo “al fondo a la derecha”, pero no es preciso, de hecho, con unos pocos ciclos del procesador se puede resolver el problema.
Supongamos que los mapas están representados por cadenas de bits y que la anchura, no excede el tamaño de palabra de nuestro procesador (hoy día, típicamente los 64 bits).
Dada la primera palabra del mapa (la de arriba), cualquier camino válido deberá estar en aquellos bits que, empezando por la derecha, sean 0 (no haya obstáculo). A partir del primer bit a 1 (por la derecha) ningún camino será válido (recuerda que son caminos tipo “al fondo a la derecha”).
Así, si tenemos la palabra 000100, cualquier camino válido sólo podrá estar en los dos primeros bits (ojo, los primeros son los de la derecha). Y tendremos que invalidar cualquiera de la izquierda, es decir, quedaría 111100.
Supuesto existe un bit a 1 ¿cómo poner todos los bits de su izquierda a 1? (como en el ejemplo). Plegando ese bit a la izquierda de forma que se acumulen. Supón que el primer bit a 1 está en la posición n, si desplazamos a la izquierda la palabra y hacemos OR consigo misma, ahora el bit n-1 estará a 1 también. Si ahora desplazamos dos posiciones la izquierda y hacemos otro OR serán las posiciones n, n-1, n-2 y n-3 las que estarán a 1. Repitiendo unas pocas veces, habremos conseguido el objetivo. Por ejemplo, para una palabra de 64 bits, basta con hacer la operación 6 veces.
w = fila1; w |= w << 1; w |= w << 2; w |= w << 4; w |= w << 8; w |= w << 16; w |= w << 32;
Para el resto de filas del mapa únicamente es necesario hacer un OR con el valor que tenemos, es decir, vamos acumulando:
a = w; a |= fila2; a |= fila3; ... a |= filaN;
Entonces, para responder si hay un camino o no en el mapa, basta ver si en los bits que hemos dejado a 0 en la primera fila, ha quedado algún 0 en el valor acumulado. ¿Sabrías como calcularlo a partir de w y de a?, recuerda, si en los bits que tiene w a 0 hay en a algún 0, entonces sí hay camino, en otro caso, no hay camino en el mapa.
Tres en raya
A cada movimiento de un jugador de tres en raya, debemos comprobar si ha ganado o no, por supuesto podemos iterar sobre las alineaciones posibles pero, ¡es más divertido hacerlo con bits!.
Supón que para cada jugador mantenemos una palabra de 9 bits (representamos una partida entera ¡con 18 bits!), dejando un 0 si el jugador no ha puesto ficha en esa posición o un 1 si sí ha puesto ficha en esa posición.
Entonces, analizar si un jugador ha ganado con su último movimiento es tan sencillo como evaluar la expresión booleana no reducible:
a b c + d e f + g h i + a d g + b e h + c f i + a e i + g e c
Por ver un ejemplo, una implementación en C de la idea anterior sería:
Combinaciones sin repetición
Como programadores, todos los días nos vemos con la necesidad de agrupar los elementos de un conjunto, el otro día sin ir mas lejos, comentaba la forma de resolver el Kata Potter y para ello precisábamos obtener las combinaciones de elementos tomadas de uno en uno, de dos en dos, … (vaya, todas las combinaciones).
Si tenemos N elementos, una forma de obtener todas las combinaciones sin repetición es enumerar de 0 a 2N-1. De forma que, si un bit está a 0, el elemento no forma parte de la combinación, si está a 1 sí (o al revés si conviene, claro).
¿Te has fijado en la forma de contar los bits?, ¿fantástico verdad?.
Además, podemos fácilmente aplicar restricciones a las combinaciones buscadas. Por ejemplo, combinaciones de entre M y M’ elementos, combinaciones en que algún elemento de un subgrupo debe estar siempre presente, etc…
Por supuesto que, en general y si no necesitamos todas las combinaciones, hay mejores formas de obtener determinados grupos de combinación (eg. combinaciones tomadas sólo de M en M). Pero si son pocos elementos (o necesitamos todas las combinaciones) es más rápido y cómodo usar alguna variante del esquema anterior. ¿Hasta cuantos? pues depende mucho, pero a partir de 25 elementos deberías buscar mejores alternativas.
Buscando ceros
Cuando aprendes C, aprendes a trabajar con cadenas terminadas en cero, por tanto, en muchas situaciones te ves buscando un cero u otro valor dentro de una cadena, por ejemplo, escribiendo algo como:
Y te dices a ti mismo lo machote que eres porque son funciones preciosas (bueno la segunda tiene un bug ¿sabrías encontrarlo?). Y un día, descubres con estupor que puede hacerse leyendo la cadena, no caracter a caracter, ¡sino de palabra en palabra!, es decir, en un procesador de 32 bits, de 4 en 4, en un procesador de 64 bits ¡de 8 en 8 bytes!.
Por supuesto que ahora requerimos una preparación mucho mayor para usar este (pedazo) de speedup, pues dada una cadena en memoria, los primeros bytes pueden no estar alineados a la palabra y los últimos no corresponder con un múltiplo de palabra.
Obviamente este es sólo otro (para mí legendario) ejemplo de que un algoritmo puede ser mejorado si pensamos en términos de bits, hoy en día los procesadores tienen instrucciones como pcmpeqb (MMX) que te permiten realizar la operación ¡sobre 16 bytes! que mejoran sin duda lo anterior, pero al que no quitan ni un ápice de mérito.
Así que ya sabes, no pierdas de vista los bits, ¡pueden serte de utilidad!.
En Genbeta Dev | Optimizando al máximo: Bitvectores
Más información | Bit Twiddling Hacks
