C/C++ efficient bit array

Since you mention C as well as C++, I'll assume that a C++-oriented solution like boost::dynamic_bitset might not be applicable, and talk about a low-level C implementation instead. Note that if something like boost::dynamic_bitset works for you, or there's a pre-existing C library you can find, then using them can be better than rolling your own.

Warning: None of the following code has been tested or even compiled, but it should be very close to what you'd need.

To start, assume you have a fixed bitset size N. Then something like the following works:

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

As written, this is a bit crude since it implements only a single global bitset with a fixed size. To address these problems, you want to start with a data struture something like the following:

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

and then write functions to create and destroy these 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);}

Now, it's relatively straightforward to modify the previous functions to take a struct bitset * parameter. There's still no way to re-size a bitset during its lifetime, nor is there any bounds checking, but neither would be hard to add at this point.

boost::dynamic_bitset if the length is only known in run time.

std::bitset if the length is known in compile time (although arbitrary).

I've written a working implementation based off Dale Hagglund's response to provide a bit array in C (BSD license).

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

Please let me know what you think / give suggestions. I hope people looking for a response to this question find it useful.