C/C++ matriz de bits eficiente

Question

¿Se puede recomendar la forma eficiente/limpia de manipular la matriz de bits de longitud arbitraria?

En este momento estoy usando la máscara de bits int/char regular, pero esas no son muy claras cuando la longitud de la matriz es mayor que la longitud del tipo de datos.

std vector<bool> no está disponible para mí.

Answer 1

boost::dynamic_bitset si la longitud solo se conoce en tiempo de ejecución.

std::bitset si la longitud se conoce en tiempo de compilación (aunque arbitraria).

Answer 2

Puede utilizar 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; 
    } 
} 

Answer 3

Ya que mencionas C, así como C++, voy a suponer que un C++ - orientado a la solución como boost::dynamic_bitset podría no ser aplicable, y hablan de una implementación de bajo nivel C en lugar. Tenga en cuenta que si algo como boost::dynamic_bitset funciona para usted, o que hay una biblioteca de C preexistente que puede encontrar, entonces usarlas puede ser mejor que rodar la suya.

Advertencia: Ninguno de los siguientes códigos ha sido probado o compilado, pero debe estar muy cerca de lo que usted necesita.

Para empezar, supongamos que tiene un tamaño N. bitset fijo Entonces algo así como las siguientes obras:

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 un solo bitset global con un tamaño fijo . Para hacer frente a estos problemas, que desea iniciar con una estrutura de datos algo como lo siguiente:

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

y luego escribir funciones para crear y destruir estos bitsets.

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 de modificar las funciones anteriores para tomar un parámetro struct bitset *. Todavía no hay forma de cambiar el tamaño de un conjunto de bits durante su ciclo de vida, ni hay ninguna comprobación de límites, pero ninguno sería difícil de agregar en este punto.

Answer 4

He escrito una implementación operativa basada en Dale Hagglund's response para proporcionar una matriz de bits en C (licencia BSD).

https://github.com/noporpoise/BitArray/

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

Answer 5

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

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

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

Vea a continuación un extracto del doco. Mana es http://alfredo4570.net/src/alflb_doco/alflb.pdf, biblioteca es http://alfredo4570.net/src/alflb.zip

Enjoy,
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. 
//------------------------------------------------------------------ 

Answer 6

Sé que es una entrada antigua pero vine aquí para encontrar un simple aplicación C bitset y ninguna de las respuestas bastante coincidía con lo que estaba buscando, así que implementé el mío basado en la respuesta de Dale Hagglund. Aquí es :)

#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; 
} 

Answer 7

utilizo éste:

//#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)) 

Answer 8

recientemente he publicado BITSCAN, una biblioteca C++ cadena de bits que está orientada específicamente a las operaciones de escaneo poco rápido. BITSCAN está disponible here. Está en alfa pero todavía está bastante probado ya que lo he usado en los últimos años para la investigación en optimización combinatoria (por ejemplo, en BBMC, un algoritmo de camarilla máximo exacto del estado de la técnica). Se puede encontrar una comparación con otras implementaciones bien conocidas de C++ (STL o BOOST) here.

Espero que lo encuentres útil. Cualquier comentario es bienvenido

Answer 9

En el desarrollo de microcontroladores, algunas veces tenemos que usar matriz 2-dimentional (matriz) con el valor del elemento de [0, 1] solamente. Eso 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 una matriz de 1 bit (el tipo de elemento es 1 bit).

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