Bit twiddling un montón de bits en C

Me gustaría usar indicadores binarios para representar un conjunto matemático en C, donde “Bit i se establece” significa “el elemento i está en el Conjunto”. Esto es conveniente porque las operaciones como “union” y “intersection” son triviales de implementar (“|” y “&”). Sin embargo, quiero que mi conjunto pueda contener más de 32 elementos. Además, quiero que mi código funcione en máquinas de 32 y 64 bits.

¿Hay alguna forma sencilla de manipular más de una palabra de bits en C? ¿Hay una mejor manera de abordar esta tarea?

Sí, simplemente define una matriz de sus enteros de 32 bits. Luego manipulas un elemento específico de la matriz.

Dado un ID de bit de 0 a 255 inclusive (por ejemplo), sería una matriz:

unsigned int bits[8]; 

Para encontrar en qué elemento operar:

 unsigned int index = bitId >> 5; // turns 0..255 into 0..31 

Para obtener las máscaras para un ID de bit dado:

 unsigned int masks[] = { 0x0001, 0x0002, 0x0004, 0x0008, 0x0001, 0x0020, 0x0040, 0x0080, 0x0100, 0x0200, 0x0400, 0x0800, 0x1000, 0x2000, 0x4000, 0x8000 }; unsigned int mask = masks[bitId & 0x1f]; 

Si tiene el tipo uint32_t disponible en su implementación, esa es probablemente la forma más segura de hacerlo. De lo contrario, hay métodos conocidos para usar unsigned int utilizando CHAR_BIT y sizeof para determinar realmente en tiempo de ejecución qué tan grande es la matriz de masks y qué valores debe usar para descubrir el índice de matriz y el índice de máscara de bits.

Por ejemplo, este fragmento de mi biblioteca de códigos muestra cómo lo hice para una máscara de bits basada en caracteres:

 static unsigned char bitmask[CHAR_BIT]; void bitsetInit (void) { unsigned char mask = 1; int i = 0; while (i < CHAR_BIT) { bitmask[i++] = mask; mask <<= 1; } } 

y usando:

 bsp->bits[bitnum/CHAR_BIT] &= ~bitmask[bitnum%CHAR_BIT]; bsp->bits[bitnum/CHAR_BIT] |= bitmask[bitnum%CHAR_BIT]; 

para borrar y ajustar bits respectivamente.

Si quisiera usar unsigned int lugar de caracteres unsigned char , simplemente calcularía la cantidad de bits para eso:

 unsigned int UINT_BIT = CHAR_BIT * sizeof (unsigned int); 

y CHAR_BIT donde he usado CHAR_BIT arriba (la matriz de mask puede asignarse dinámicamente en tiempo de ejecución si es necesario).

La biblioteca Gnu de precisión múltiple proporciona una implementación de enteros, con una optimización muy buena para enteros de precisión arbitraria, y también tiene la funcionalidad más útil de twiddling de bits. (enlazar)

Dependiendo de las operaciones específicas que realmente necesite realizar, puede haber algunas estructuras de datos sofisticadas que podrían hacer el trabajo un poco mejor. Por ejemplo, existe una estructura muy inteligente de conjuntos disjuntos, para modelar un conjunto de conjuntos disjuntos, que tiene un rendimiento asintótico realmente sorprendente en las 3 operaciones que admite.

Podría usar uint64_t desde . Más allá de eso, me temo que estás fuera de suerte en cuanto a & y | están preocupados y deben buscar un diseño diferente (por ejemplo, estructuras con funciones apropiadas para manejarlas o bibliotecas de terceros).

paxdiablo parece haberle dado el enfoque correcto para resolver este problema de la manera que dijo que quiere resolverlo.

¿Hay una mejor manera de abordar esta tarea?

A menos que tenga un rendimiento específico o una razón de hardware para realizar su trabajo a nivel de bits, podría haber mejores formas de representar un conjunto. Por ejemplo, una lista enlazada o un árbol binario, cuyos valores son miembros del conjunto. Ambas estructuras pueden tener (efectivamente) un tamaño infinito y son fáciles de recorrer.

El hecho de que algunas operaciones de conjunto sean fáciles de implementar con lógica booleana no significa que todas lo sean. El código adicional que depende de sus operaciones de configuración será más claro si tiene una interfaz de tipo de configuración, en lugar de una interfaz de lógica booleana (solo).

Independientemente de la solución que encuentre, le recomiendo que la esconda detrás de una interfaz, para que pueda cambiar su solución de almacenamiento en el futuro. Puede hacer esto definiendo funciones a las que le pasa su estructura y operando solo en la estructura a través de esas funciones.

Si realmente está satisfecho con los tipos de 32 y 64 bits, en C moderno (también conocido como C99) se garantiza que uint_least64_t uint_least32_t y uint_least64_t existen en "stdint.h" . En contraste con los tipos de ancho exacto uint32_t y uint64_t (que son opcionales) pueden corresponder a un tipo base que tiene un ancho que es más ancho que el número indicado.

Si la velocidad es importante, también puede usar uint_fast32_t y uint_fast64_t que también deben existir. Cambian la velocidad por el tamaño y se supone que deben usar el tipo base correspondiente que tiene el soporte “más rápido” en la máquina de destino. Sin embargo, la explosión de datos puede ser sustancial. Por ejemplo, en mi ubuntu de 64 bits, todos estos tipos “rápidos” son de 64 bits.

Si usa gcc, también tendrá __uint128_t en máquinas de 64 bits como un servicio adicional.