How to implement bit set in C?

Question

I use the Bitset class in Java, and I would like to do something similar in C. I suppose I have to do it manually like most things in C. What would be an efficient way to implement it?

byte bitset[] 

may be

 bool bitset[] 

?

Answer 1

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

But if you end up implementing it yourself (for example, if you don't like the dependencies on this package), you should use an int array 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)); } 

Do not use a specific size (for example, with uint64 or uint32), let the computer use what it wants to use and adapt to it using sizeof.

Answer 2

No one mentioned that it recommends the C FAQ, 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 )

Answer 3

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

Use bit fields in the structure, and then you can maintain a collection of these types (or use them anyway you like)

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

Answer 4

I recommend the BITSCAN C ++ library (version 1.0 has just been released). BITSCAN is specifically focused on fast bit operations. I used it to implement NP-Hard combinatorial problems using simple undirected graphs, such as maximum click (see BBMC algorithm for a leading exact solver).

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

Answer 5

You can request the PackedArray code bitsPerItem 1 .

It implements a random access container where elements are packed at the bit level. In other words, it acts as if you can manipulate, for example, uint9_t or uint17_t :

 PackedArray principle: . compact storage of <= 32 bits items . items are tightly packed into a buffer of uint32_t integers PackedArray requirements: . you must know in advance how many bits are needed to hold a single item . you must know in advance how many items you want to store . when packing, behavior is undefined if items have more than bitsPerItem bits PackedArray general in memory representation: |-------------------------------------------------- - - - | b0 | b1 | b2 | |-------------------------------------------------- - - - | i0 | i1 | i2 | i3 | i4 | i5 | i6 | i7 | i8 | i9 | |-------------------------------------------------- - - - . items are tightly packed together . several items end up inside the same buffer cell, eg i0, i1, i2 . some items span two buffer cells, eg i3, i6 

Answer 6

As usual, you first need to decide what operations you need to perform on your bitet. Perhaps some subset of what Java defines? After that, you can decide how best to implement it. You can of course look at the source for BitSet.java in OpenJDK for ideas.

Answer 7

Make the array an unsigned int 64 array.