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

Question

I am doing a project that includes solving some problems with NP-hard graphics. Specifically, triangulation of Bayesian networks ...

In any case, I use std :: bitset to create an adjacency matrix, and this is very nice ... But I would like to scan the bitset using the bsf instruction. For instance. not using a while loop.

Does anyone know if this is possible?

Answer 1

Looking at the STL, which comes with gcc 4.0.0, methods of bits _Find_firstand _Find_nextare already doing what you want. In particular, they use __builtin_ctzl()(described here ), which should use the appropriate instruction. (I would suggest that the same applies to older versions of gcc.)

And the best part is that the bitrate is already doing the right thing: one instruction, if it is a bitset that fits into one unsigned long; loop over long if it uses multiple. In the case of a loop, this is a loop whose length is known at compile time, with several instructions, so it can be fully deployed by the optimizer. That is, it would probably be difficult to beat bits, fettering your own.

Answer 2

std::bitset::to_ulong, BSF ( - , 32 , - 32/64.

BSF MSVC _BitScanForward -

BitMagic

Answer 3

Perhaps you can consider the BITSCAN C ++ Library for manipulating an array of bits and Ugraph for managing non-directional graphs with bit encoding. Since this is my code, I will not add additional comments to this.

Hope this helps! (If this is interesting, I will be interested in any feedback).