tags:

views:

52

answers:

2

Hi,

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?

A: 

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

Necrolis
I've had a look at BitMagic, but it's dynamic sizes, and I can get more speed with static sizes...And to_ulong() is defined to throw an exception if the bitset is larger than a unsigned long, so that won't do it...
jopsen
Would a vector of 32-bit bitsets help?
Mark B
Imo, the best option is to roll your own class, then you can integrate the bsf into the class. And std::bitset can be used as a base, seeing as its source is given in the header
Necrolis
+1  A: 

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.

DS
Okay, I suppose it would be best to make a struct that wraps std:bitset methods, so that missing functionality could be implemented for other compilers/systems using #ifdefs...- Thanks...
jopsen