Código del Día: Determinar si los bits en un número son continuos

Leonardo Herrera
Creado: 12/11/2003
Última Actualización: 21/9/2004
Parte de Código del Día

Uf, se me había olvidado el Código del Día. Acá va una pequeña función en C, que permite saber si los bits en un número son continuos. No, no tiene nada que ver con conjuntos ni funciones. Es simplemente para saber si no hay 0's entre dos o más 1's.

A pesar de que parece un ejercicio inútil, esta función nació de una necesidad real. En mi trabajo, tuve que escribir una función que expresaba en palabras una recurrencia, un evento que estaba programado que ocurriese en ciertas ocasiones. Por ejemplo, un proceso se iba a ejecutar una vez al día, o los lunes o los martes, o los días 1, 2, y 3 de cada mes, etc. Es posible que un proceso -en este caso, un envío de correos- se ejecute todos los días, o sólo de Lunes a Viernes, por ejemplo.

Buscando maneras de representar un rango de una manera simple en una base de datos, con Marito investigamos cómo estaban organizados los triggers (llamados tigres con cariño) en Sybase, y ocurre que usaban un byte cuando el rango era semanal, o un entero de 32 bits cuando el rango era mensual. Si el último bit estaba encendido, quería decir "toda la semana" o "todo el mes". Pero estoy alejándome del problema a la mano.

Una vez que tuve el valor de la recurrencia almacenado en un número (donde, por ejemplo, el primer bit representa el lunes, el segundo el martes, etc., en el caso de la semana) necesitaba desplegar el texto. Y me salía lo siguiente:

Ejecutar todos los Lunes, Martes, Miércoles, Jueves y Viernes.

No era tan malo. Pero cuando llegó la hora de mostrar la recurrencia para un mes, podía encontrar lo siguiente:

Ejecutar todos los 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 y 20 de cada mes.

Oh, y eso que hay más días en el mes. Ese mensaje no era presentable. Así que decidí dejarlo de la siguiente forma:

Ejecutar de Lunes a Viernes.

Ejecutar desde el 2 al 20 de cada mes.

Así que me encontré con la necesidad de jugar un poco. Estoy casi seguro de que debe existir, por ahí, alguna función, propiedad matemática, axioma, teoría de conjuntos o etcéteras que determine, en un simple paso, si los bits en un conjunto de bytes son contiguos (después de todo, son números). Probablemente, hasta exista una progresión en estos números. Ahora que lo pienso, la voy a buscar. Pero, en el interanto, acá está la función que usé para solucionar este problema. Está en C, y muestra los bits encendidos en el byte, así que es fácil de comprobar visualmente.

#include <stdio.h>

int continuo( int bitmask )
{
    char c[33];
    char i, co = 0, st = 0, fn = 0, cb;
    for (i=0; i < 32; i++ ) {
        // cb significa "current bit"
        cb = (bitmask & (1 << i)) ? 1 : 0;
        // Acá sólo almacenamos el string que se desplegará más
        // abajo.
        c[31-i] = (cb) ? '1': '0';
        // co indica si es continuo. Se inicializa al encontrar
        // el primer bit activo.
        co |= (!st && cb);
        // st indica que encontramos el bit de inicio.
        // Se hace verdadero al encontrar el primer bit encendido.
        st |= cb;
        // fn se activa apenas encontramos un bit apagado, después
        // de haber hallado un bit anterior encendido.
        fn |= (st && !cb);
        // Es continuo, mientras estemos dentro de un "segmento".
        // Si encontramos un bit activo despues de haber finalizado
        // un segmento, esta expresión se vuelve falsa, por lo que
        // se "apaga" el flag "co".
        co &= ((cb && !fn) || (fn && !cb));
    }
    c[32] = '\0';
    printf( "continuo(%s) : %d\n", c, co );
    return co;
}

int main()
{
    int i;
    for (i=0; i < 20; i++ )
        continuo( i );
    return 1;
}

Esto retorna lo siguiente:

leus@desarrollo:~> gcc test.c
leus@desarrollo:~> ./a.out
continuo(00000000000000000000000000000000) : 0
continuo(00000000000000000000000000000001) : 1
continuo(00000000000000000000000000000010) : 1
continuo(00000000000000000000000000000011) : 1
continuo(00000000000000000000000000000100) : 1
continuo(00000000000000000000000000000101) : 0
continuo(00000000000000000000000000000110) : 1
continuo(00000000000000000000000000000111) : 1
continuo(00000000000000000000000000001000) : 1
continuo(00000000000000000000000000001001) : 0
continuo(00000000000000000000000000001010) : 0
continuo(00000000000000000000000000001011) : 0
continuo(00000000000000000000000000001100) : 1
continuo(00000000000000000000000000001101) : 0
continuo(00000000000000000000000000001110) : 1
continuo(00000000000000000000000000001111) : 1
continuo(00000000000000000000000000010000) : 1
continuo(00000000000000000000000000010001) : 0
continuo(00000000000000000000000000010010) : 0
continuo(00000000000000000000000000010011) : 0
leus@desarrollo:~>

Consultas, enviar a mi correo electrógeno.

Este sitio es mantenido con ePublish