Encontrar la primera aparición de un patrón P dentro de un texto T es un problema clásico de la informática. Junto a soluciones conocidas como Boyer-Moore, Knuth-Morris-Pratt o el algoritmo de dos vías, existe una alternativa menos divulgada llamada bitap (o shift-and), especialmente eficiente cuando el patrón cabe en una palabra de máquina (menos de 64 caracteres). Su atractivo reside en una combinación singular: resulta sencilla de comprender y de programar, ofrece un rendimiento notable con cadenas cortas y aprovecha las operaciones a nivel de bit de forma muy elegante.
El artículo expone el algoritmo de manera progresiva, partiendo del método de fuerza bruta que prueba el patrón en cada posición posible del texto. A partir de ahí, se reformula para operar sobre un flujo de caracteres, manteniendo un conjunto de coincidencias en curso mientras se recorre el texto de izquierda a derecha. Cada coincidencia parcial se representa por el índice del siguiente carácter del patrón que se espera leer; cuando un carácter del flujo no coincide, esa coincidencia parcial se descarta.
La clave de bitap llega al comprimir ese conjunto de estados activos en un único entero de 64 bits, interpretado como un mapa de bits. En lugar de iterar por cada estado para comprobar si puede avanzar, el algoritmo desplaza todos los estados una posición a la izquierda con una sola operación (active << 1) y elimina los estados inválidos intersectando con una máscara precalculada que indica qué transiciones son válidas para el carácter actual. Cada carácter del patrón tiene asociada una máscara de bits con las posiciones desde las que puede avanzar.
El resultado es un bucle interno sin iteraciones explícitas: unas pocas instrucciones a nivel de bit procesan cada carácter del texto. La limitación principal es clara: el patrón debe ser más corto que el ancho de la palabra del procesador (64 bits en máquinas actuales). Para búsquedas dentro de archivos, filtros de spam, detección de firmas o herramientas como grep, bitap ofrece una solución compacta y rápida, aunque para patrones largos conviene recurrir a los algoritmos clásicos mencionados.