bitscan (bsf) on std::bitset ? Or similar

Question

I'm doing a project that involves solving some NP-hard graph problems. Specifically triangulation of Bayesian networks...

Anyway, I'm using std::bitset for creating an adjacency matrix and this is very nice... But I would like to scan the bitset using a bsf instruction. E.g. not using a while loop.

Anybody know if this is possible?

Answer 1

Looking at the STL that comes with gcc 4.0.0, the bitset methods _Find_first and _Find_next already do what you want. Specifically, they use __builtin_ctzl() (described here), which should use the appropriate instruction. (I would guess that the same applies for older versions of gcc.)

And the nice thing is that bitset already does the right thing: single instruction if it's a bitset that fits within a single unsigned long; a loop over the longs if it uses several. In case of a loop, it's a loop whose length is known at compile time, with a handful of instructions, so it might be fully unrolled by the optimizer. I.e. it would probably be hard to beat bitset by rolling your own.

Answer 2

Use std::bitset::to_ulong and then BSF it(you'll need a custom contian for something bigger that 32bits though, or some way to get references to each 32/64 set of bits.

for BSF on MSVC you can use _BitScanForward else you can use something from here

You might also want to look into using BitMagic instead

Answer 3

Possibly you might consider looking at BITSCAN C++ library for bit array manipulation and Ugraph for managing bit-encoded undirected graphs. Since it is my code I will not add additional comments on this.

Hope it helps! (If it does I would be interested in any feedback).