C/C++ efficace tableau de bits

Puisque vous parlez de C et de C++, je vais supposer que C++orienté solution comme boost::dynamic_bitset pourraient ne pas être applicables, et de parler d'un faible niveau C mise en place. Notez que si quelque chose comme boost::dynamic_bitset qui fonctionne pour vous, ou il y a une pré-existant de la bibliothèque C, vous pouvez trouver, puis de les utiliser peut être mieux que rouler votre propre.

Avertissement: Aucun des éléments suivants du code a été testé ou même compilé, mais il devrait être très proche de ce que vous avez besoin.

Pour commencer, supposons que vous disposez d'un fixe bitset taille N. Alors quelque chose comme les ouvrages suivants:

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

Comme l'a écrit, c'est un peu brut, car il met en œuvre une seule mondial bitset avec une taille fixe. Pour remédier à ces problèmes, vous voulez commencer avec une base de données struture quelque chose comme ce qui suit:

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

et puis écrire les fonctions permettant de créer et de détruire ces 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);
}

Maintenant, il est relativement facile de modifier les fonctions précédentes de prendre un struct bitset * paramètre. Il n'y a toujours pas moyen de re-dimensionner un bitset au cours de sa vie, ni de la vérification des limites, mais ni serait difficile d'ajouter à ce point.

Ce message est un peu vieux, mais il est efficace d'un tableau de bits de la suite dans C dans mon ALFLB bibliothèque.

Pour de nombreux microcontrôleurs sans matériel-division de l'opcode, cette bibliothèque est EFFICACE parce qu'elle n'utilise pas de division: au lieu de cela, de masquage et de décalage de bits sont utilisés. (Oui, je sais que certains compilateurs convertir division par 8 pour un quart, mais cela varie d'un compilateur de compilateur.)

Il a été testé sur les tableaux jusqu'à 2^32-2 bits (environ 4 milliards de bits stockés dans 536 Mo), bien que les 2 derniers bits doit être accessible, si ce n'est pas dans une boucle for dans votre application.

Voir ci-dessous un extrait de la doco. Doco est http://alfredo4570.net/src/alflb_doco/alflb.pdf, la bibliothèque est http://alfredo4570.net/src/alflb.zip

Profiter,

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

Je sais que c'est un vieux post, mais je suis venu ici pour trouver un simple C bitset la mise en œuvre et aucune des réponses tout à fait se comparer à ce que je cherchais, alors j'ai mis en place mon propre basée sur Dale Hagglund de réponse. Ici, il 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;
}

J'ai récemment publié BITSCAN, C++ chaîne de bits de la bibliothèque qui est spécifiquement orientée vers d'échantillonnage rapide de la numérisation. BITSCAN est disponible ici. Il est en alpha, mais encore assez bien testé depuis que je l'ai utilisé ces dernières années pour la recherche en optimisation combinatoire (par exemple, dans BBMC, un état de l'art exacte de la clique maximale de l'algorithme). Une comparaison avec d'autres bien connus C++ implémentations STL (ou BOOST) peut être trouvé ici.

J'espère que vous le trouverez utile. Tout commentaire est le bienvenu.