Matrice di bit efficiente C/C++

Question

Si può consigliare un modo efficiente/pulito per manipolare array di bit di lunghezza arbitraria?

In questo momento sto usando la normale maschera di bit int/char, ma quelli non sono molto puliti quando la lunghezza dell'array è maggiore della lunghezza del tipo di dati.

std vector<bool> non disponibile per me.

Answer 1

boost::dynamic_bitset se la lunghezza è nota solo in fase di esecuzione.

std::bitset se la lunghezza è nota in fase di compilazione (anche se arbitraria).

Answer 2

È possibile utilizzare 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

Dal momento che si parla di C così come C++, darò per scontato che un C++ - orientato soluzione come boost::dynamic_bitset potrebbe non essere applicabile, e parlare di un'implementazione a basso livello C anziché. Nota che se qualcosa come boost::dynamic_bitset funziona per te, o c'è una libreria C pre-esistente che puoi trovare, allora usarli può essere meglio che lanciare il tuo.

Avviso: nessuno dei seguenti codici è stato testato o anche compilato, ma dovrebbe essere molto vicino a quello che ti serve.

Per iniziare, suppone che si abbia una dimensione N. bitset fissa Poi qualcosa come le seguenti opere:

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 */ } 

Come scritto, questo è un po 'cruda in quanto implementa una sola bitset globale con una dimensione fissa . Per affrontare questi problemi, si vuole iniziare con un qualcosa di dati struture come il seguente:

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

e poi scrivere funzioni per creare e distruggere queste bitset.

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

Ora, è relativamente semplice per modificare le funzioni precedenti per prendere un parametro struct bitset *. Non c'è ancora modo di ridimensionare un bitset durante la sua vita, né ci sono limiti di controllo, ma non sarebbe difficile aggiungere a questo punto.

Answer 4

Ho scritto un'implementazione di lavoro basata su Dale Hagglund's response per fornire un array di bit in C (licenza BSD).

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

Per favore fatemi sapere cosa ne pensate/dare suggerimenti. Spero che le persone in cerca di una risposta a questa domanda lo trovino utile.

Answer 5

Questo post è piuttosto vecchio, ma c'è una suite di array di bit efficiente in C nella mia libreria ALFLB.

Per molti microcontrollori senza un codice operativo della divisione hardware, questa libreria è EFFICIENTE perché non utilizza la divisione: invece, vengono utilizzati il ​​masking e il bit-shifting. (Sì, so che alcuni compilatori convertiranno la divisione per 8 in un turno, ma questo varia dal compilatore al compilatore.)

È stato testato su matrici fino a 2^32-2 bit (circa 4 miliardi di bit memorizzati in 536 MByte), anche se gli ultimi 2 bit dovrebbero essere accessibili se non utilizzati in un ciclo for nella propria applicazione.

Vedere di seguito un estratto dal documento. Doco è http://alfredo4570.net/src/alflb_doco/alflb.pdf, biblioteca è http://alfredo4570.net/src/alflb.zip

godere,
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

Lo so che è un vecchio post, ma sono venuto qui per trovare una semplice implementazione C bitset e nessuna delle risposte abbastanza abbinato quello che ero cercando, quindi ho implementato il mio basato sulla risposta di Dale Hagglund. Qui è :)

#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

Io uso questo:

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

Ho recentemente rilasciato BITSCAN, una biblioteca stringa di bit C++ che è specificamente orientata verso operazioni di scansione veloce bit. BITSCAN è disponibile here. È in alpha ma è ancora abbastanza ben collaudato da quando l'ho usato negli ultimi anni per la ricerca nell'ottimizzazione combinatoria (ad esempio in BBMC, un algoritmo di clique massimo esatto allo stato dell'arte). Un confronto con altre ben note implementazioni C++ (STL o BOOST) può essere trovato here.

Spero che lo trovi utile. Qualsiasi commento è benvenuto.

Answer 9

Nello sviluppo di microcontrollori, alcune volte è necessario utilizzare array a 2 dimensioni (matrice) con il solo valore di elemento [0, 1]. Che significa che se usiamo 1 byte per tipo di elemento, spreca molto la memoria (la memoria del microcontrollore è molto limitata). La soluzione proposta è che dovremmo usare una matrice a 1 bit (il tipo di elemento è 1 bit).

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