Matriz de bits eficiente C / C++

Dado que mencionas tanto C como C++, asumiré que una solución orientada a C++como boost::dynamic_bitset podría no ser aplicable, y hablaré de una implementación de C de bajo nivel en su lugar. Tenga en cuenta que si algo como boost::dynamic_bitset funciona para usted, o hay una biblioteca C preexistente que puede encontrar, entonces usarlos puede ser mejor que rodar la suya propia.

Advertencia : Ninguno de los siguientes códigos ha sido probado o compilado, pero debería estar muy cerca de lo que necesitarías.

Para empezar, asume que tener un tamaño de bitset fijo N. Entonces algo como lo siguiente funciona:

typedef uint32_t word_t;
enum { WORD_SIZE = sizeof(word_t) * 8 };

word_t data[N / 32 + 1];

inline int bindex(int b) { return b / WORD_SIZE; }
inline int boffset(int b) { return b % WORD_SIZE; }

void set_bit(int b) { 
    data[bindex(b)] |= 1 << (boffset(b)); 
}
void clear_bit(int b) { 
    data[bindex(b)] &= ~(1 << (boffset(b)));
}
int get_bit(int b) { 
    return data[bindex(b)] & (1 << (boffset(b));
}
void clear_all() { /* set all elements of data to zero */ }
void set_all() { /* set all elements of data to one */ }

Como está escrito, esto es un poco crudo ya que implementa solo un único conjunto de bits global con un tamaño fijo. Para abordar estos problemas, desea comenzar con una estructura de datos algo como lo siguiente:

struct bitset { word_t *words; int nwords; };

Y luego escribir funciones para crear y destruir estos conjuntos de bits.

struct bitset *bitset_alloc(int nbits) {
    struct bitset *bitset = malloc(sizeof(*bitset));
    bitset->nwords = (n / WORD_SIZE + 1);
    bitset->words = malloc(sizeof(*bitset->words) * bitset->nwords);
    bitset_clear(bitset);
    return bitset;
}

void bitset_free(struct bitset *bitset) {
    free(bitset->words);
    free(bitset);
}

Ahora, es relativamente sencillo modificar las funciones anteriores para tomar un parámetro struct bitset *. Todavía no hay manera de cambiar el tamaño de un bitset durante su vida útil, ni hay ninguna comprobación de límites, pero ninguno sería difícil de añadir en este punto.

He escrito una implementación de trabajo basada en La respuesta de Dale Hagglund para proporcionar una matriz de bits en C (licencia BSD).

Https://github.com/noporpoise/BitArray /

Por favor, hágame saber lo que piensa / dar sugerencias. Espero que las personas que buscan una respuesta a esta pregunta la encuentren útil.

Esta publicación es bastante antigua, pero hay una eficiente suite de matrices de bits en C en mi biblioteca ALFLB.

Para muchos microcontroladores sin un opcode de división de hardware, esta biblioteca es EFICIENTE porque no usa división: en su lugar, se usa enmascaramiento y desplazamiento de bits. (Sí, sé que algunos compiladores convertirán división por 8 a un cambio, pero esto varía de compilador a compilador.)

Se ha probado en matrices de hasta 2^32-2 bits (alrededor de 4 mil millones de bits almacenados en 536 MBytes), aunque los últimos 2 bits deben ser accesibles si no se usan en un bucle for en su aplicación.

Véase a continuación un extracto de la doco. Doco es http://alfredo4570.net/src/alflb_doco/alflb.pdf, la biblioteca es http://alfredo4570.net/src/alflb.zip

Disfrutar,
Alf

//------------------------------------------------------------------
BM_DECLARE( arrayName, bitmax);
        Macro to instantiate an array to hold bitmax bits.
//------------------------------------------------------------------
UCHAR *BM_ALLOC( BM_SIZE_T bitmax); 
        mallocs an array (of unsigned char) to hold bitmax bits.
        Returns: NULL if memory could not be allocated.
//------------------------------------------------------------------
void BM_SET( UCHAR *bit_array, BM_SIZE_T bit_index);
        Sets a bit to 1.
//------------------------------------------------------------------
void BM_CLR( UCHAR *bit_array, BM_SIZE_T bit_index);
        Clears a bit to 0.
//------------------------------------------------------------------
int BM_TEST( UCHAR *bit_array, BM_SIZE_T bit_index); 
        Returns: TRUE (1) or FALSE (0) depending on a bit.
//------------------------------------------------------------------
int BM_ANY( UCHAR *bit_array, int value, BM_SIZE_T bitmax); 
        Returns: TRUE (1) if array contains the requested value (i.e. 0 or 1).
//------------------------------------------------------------------
UCHAR *BM_ALL( UCHAR *bit_array, int value, BM_SIZE_T bitmax);
        Sets or clears all elements of a bit array to your value. Typically used after a BM_ALLOC.  
        Returns: Copy of address of bit array
//------------------------------------------------------------------
void BM_ASSIGN( UCHAR *bit_array, int value, BM_SIZE_T bit_index);
        Sets or clears one element of your bit array to your value.
//------------------------------------------------------------------
BM_MAX_BYTES( int bit_max); 
        Utility macro to calculate the number of bytes to store bitmax bits.
        Returns: A number specifying the number of bytes required to hold bitmax bits.
//------------------------------------------------------------------

Puede usar std:: bitset

int main() {
  const bitset<12> mask(2730ul); 
  cout << "mask =      " << mask << endl;

  bitset<12> x;

  cout << "Enter a 12-bit bitset in binary: " << flush;
  if (cin >> x) {
    cout << "x =        " << x << endl;
    cout << "As ulong:  " << x.to_ulong() << endl;
    cout << "And with mask: " << (x & mask) << endl;
    cout << "Or with mask:  " << (x | mask) << endl;
  }
}

Sé que es una publicación antigua, pero vine aquí para encontrar una implementación simple de C bitset y ninguna de las respuestas coincidía con lo que estaba buscando, así que implementé la mía basada en la respuesta de Dale Hagglund. Aquí está :)

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>

typedef uint32_t word_t;
enum { BITS_PER_WORD = 32 };
struct bitv { word_t *words; int nwords; int nbits; };

struct bitv* bitv_alloc(int bits) {
    struct bitv *b = malloc(sizeof(struct bitv));

    if (b == NULL) {
        fprintf(stderr, "Failed to alloc bitv\n");
        exit(1);
    }

    b->nwords = (bits >> 5) + 1;
    b->nbits  = bits;
    b->words  = malloc(sizeof(*b->words) * b->nwords);

    if (b->words == NULL) {
        fprintf(stderr, "Failed to alloc bitv->words\n");
        exit(1);
    }

    memset(b->words, 0, sizeof(*b->words) * b->nwords);

    return b;
}

static inline void check_bounds(struct bitv *b, int bit) {
    if (b->nbits < bit) {
        fprintf(stderr, "Attempted to access a bit out of range\n");
        exit(1);
    }
}

void bitv_set(struct bitv *b, int bit) {
    check_bounds(b, bit);
    b->words[bit >> 5] |= 1 << (bit % BITS_PER_WORD);
}

void bitv_clear(struct bitv *b, int bit) {
    check_bounds(b, bit);
    b->words[bit >> 5] &= ~(1 << (bit % BITS_PER_WORD));
}

int bitv_test(struct bitv *b, int bit) {
    check_bounds(b, bit);
    return b->words[bit >> 5] & (1 << (bit % BITS_PER_WORD));
}

void bitv_free(struct bitv *b) {
    if (b != NULL) {
        if (b->words != NULL) free(b->words);
        free(b);
    }
}

void bitv_dump(struct bitv *b) {
    if (b == NULL) return;

    for(int i = 0; i < b->nwords; i++) {
        word_t w = b->words[i];

        for (int j = 0; j < BITS_PER_WORD; j++) {
            printf("%d", w & 1);
            w >>= 1;
        }

        printf(" ");
    }

    printf("\n");
}

void test(struct bitv *b, int bit) {
    if (bitv_test(b, bit)) printf("Bit %d is set!\n", bit);
    else                   printf("Bit %d is not set!\n", bit);
}

int main(int argc, char *argv[]) {
    struct bitv *b = bitv_alloc(32);

    bitv_set(b, 1);
    bitv_set(b, 3);
    bitv_set(b, 5);
    bitv_set(b, 7);
    bitv_set(b, 9);
    bitv_set(b, 32);
    bitv_dump(b);
    bitv_free(b);

    return 0;
}

Uso este:

//#include <bitset>
#include <iostream>
//source http://stackoverflow.com/questions/47981/how-do-you-set-clear-and-toggle-a-single-bit-in-c
#define BIT_SET(a,b) ((a) |= (1<<(b)))
#define BIT_CLEAR(a,b) ((a) &= ~(1<<(b)))
#define BIT_FLIP(a,b) ((a) ^= (1<<(b)))
#define BIT_CHECK(a,b) ((a) & (1<<(b)))

/* x=target variable, y=mask */
#define BITMASK_SET(x,y) ((x) |= (y))
#define BITMASK_CLEAR(x,y) ((x) &= (~(y)))
#define BITMASK_FLIP(x,y) ((x) ^= (y))
#define BITMASK_CHECK(x,y) ((x) & (y))

Recientemente he lanzado BITSCAN, una biblioteca de cadenas de bits de C++ que está específicamente orientada hacia operaciones de escaneo rápido de bits. BITSCAN está disponible aquí . Está en alfa pero todavía bastante bien probado ya que lo he utilizado en los últimos años para la investigación en optimización combinatoria (por ejemplo, en BBMC, un algoritmo de camarilla máxima exacta de última generación). Una comparación con otras implementaciones bien conocidas de C++ (STL o BOOST) se puede encontrar aquí.

Espero que encuentres es útil. Cualquier comentario es bienvenido.

En el desarrollo de microcontroladores, algunas veces necesitamos usar matriz de 2 dimensiones (matriz) con un valor de elemento de [0, 1] solamente. Que significa que si usamos 1 byte para el tipo de elemento, desperdicia la memoria en gran medida (la memoria del microcontrolador es muy limitada). La solución propuesta es que debemos usar matriz de 1 bit (el tipo de elemento es de 1 bit).

Http://htvdanh.blogspot.com/2016/09/one-bit-matrix-for-cc-programming.html