Good library for bitsets or bitarrays

Question

Hallo all, I'm looking for some good library, that works with bitsets or bitarrays. Anybody knows something better (or not worse in all cases) then boost::dynamic_bitset? No matter if the library is open source or commercial.

In my project it is a common task to store and work with large bit masks, that contain less number of ones. So they could be compressed well in memory.

Answer 1

There are several implementations of compressed bitvectors available. They usually feature a run length encoding together with and/or/xor/not operations which work on the compressed form.

So the benefits are:

• smaller space usage (for sparse bitsets, as in your use case)
• very fast bit operations (because they work on words and are far more cpu cache friendly)

and on the downside:

• slower bit access (iteration required to find a bit at a specific position)

Some implementations i am aware of (there are others i am sure):

Fastbit Is in fact a database using a bitvector index. The compressed bitvector class can be used directly (without the indexing)

Lemur bitmapindex Another implementation of the EWAH encoding introduced by Fastbit

Compressed bitvector by koen.vandamme Never tried it...but only two headers and a cpp file. So not much effort to give it a try.

Bitmagic Full blown package implementing several compressed bitvectors including hardware support (sse2, ...)

Hope this helps,

Roland