How to implement a bitset in C?

c bitset

I have been using the Bitset class in Java and I would like to do something similar in C. I suppose I would have to do it manually as most stuff in C. What would be an efficient way to implement?

byte bitset[]

maybe

bool bitset[]

CCAN has a bitset implementation you can use: http://ccan.ozlabs.org/info/jbitset.html

But if you do end up implementing it yourself (for instance if you don't like the dependencies on that package), you should use an array of ints and use the native size of the computer architecture:

#define WORD_BITS (8 * sizeof(unsigned int))

unsigned int * bitarray = (int *)calloc(size / 8 + 1, sizeof(unsigned int));

static inline void setIndex(unsigned int * bitarray, size_t idx) {
    bitarray[idx / WORD_BITS] |= (1 << (idx % WORD_BITS));
}

Don't use a specific size (e.g. with uint64 or uint32), let the computer use what it wants to use and adapt to that using sizeof.

Nobody mentioned what the C FAQ recommends, which is a bunch of good-old-macros:

#include <limits.h>     /* for CHAR_BIT */

#define BITMASK(b) (1 << ((b) % CHAR_BIT))
#define BITSLOT(b) ((b) / CHAR_BIT)
#define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b))
#define BITCLEAR(a, b) ((a)[BITSLOT(b)] &= ~BITMASK(b))
#define BITTEST(a, b) ((a)[BITSLOT(b)] & BITMASK(b))
#define BITNSLOTS(nb) ((nb + CHAR_BIT - 1) / CHAR_BIT)

(via http://c-faq.com/misc/bitsets.html)

Well, byte bitset[] seems a little misleading, no?

Use bit fields in a struct and then you can maintain a collection of these types (or use them otherwise as you see fit)

struct packed_struct {
  unsigned int b1:1;
  unsigned int b2:1;
  unsigned int b3:1;
  unsigned int b4:1;
  /* etc. */
} packed;

I recommend my BITSCAN C++ library (version 1.0 has just been released). BITSCAN is specifically oriented for fast bitscan operations. I have used it to implement NP-Hard combinatorial problems involving simple undirected graphs, such as maximum clique (see BBMC algorithm, for a leading exact solver).

A comparison between BITSCAN and standard solutions STL bitset and BOOST dynamic_bitset is available here: http://blog.biicode.com/bitscan-efficiency-at-glance/

How to implement a bitset in C?

Related

Recent Posts