Efficient way of iterating over true bits in std::

Question

Is there a way of iterating over a (possibly huge) std::bitset that is linear in the number of bits that are set to true? I want to prevent having to check every single position in the bitset. The iteration should successively return the indices of each bit that is set to true.

Answer 1

For that to be linear, you'd need a linked-list/array/set of the indices set true. Keeping such a secondary index is not part of the performance/storage tradeoffs required by std::bitset, and given it would disadvantage everyone without your specific requirement, there's no way an implementation will provide this. You could consider supplementing your bitset with such a container yourself, or using boost's multi-index container library.

Answer 2

There are only two options that do much better than O(N) on total bits:

1. Using specialty bit-scan instructions available in certain architectures like BSF in x86.
2. There are O(log2(N)) algorithms for finding the lowest bit set in a word. This, of course does not scale well when the bitset is dense, rather than sparse. Resurrecting some foggy memory of mine, I found the source in the FXT library Details can be found in the FXT book (pdf), in section 1.3.2.

Answer 3

A standard bitvector does not support efficient iteration over true bits - the runtime is always O(n), where n is the number of total bits, which has no dependence on k. However, a special structure called a van Emde Boas Tree supports iteration over the bits in time O(k lg lg n), where n is the number of bits and k is the number of true bits.

As a bit of Shameless Self-Promotion, I have an implementation of a vEB-tree on my personal website. If it's inappropriate for me to advertise this here, please let me know and I'll take it down.

Answer 4

Looping over the entire bitset and simply checking the value and storing the index if true, IS linear. You can speed that up though with a lookup table. See this code:

http://xiangqi-engine.cvs.sourceforge.net/viewvc/xiangqi-engine/tsito2/src/Utility.cpp?revision=1.5&view=markup

Answer 5

You can check up to 32-bits at a time with a u64 accumulator and a 32-entry table like

u32 kTable[]
{
0x01, 0x03, 0x07, 0x0F ..., 0xFFFFFFFF
};

Just read in 32 bits into a u64 accumulator and shift it down depending on the offset and check your bits against the table. You can do this in a binary fashion to make the number of compares at max 5. This will be slower for data that isn't 'linear' in fashion. THis then becomes log time.

Answer 6

Sometimes people use run-length encoding for things like that. If you encode incoming bitset into an array of run lengths the number of runs you end up with wouldn't exceed the number of transitions between set and clear bits, which is at most 2*k. Furthermore, in many applications the number of transitions is much less than k, so you'd get excellent average time performance in addition to linear worst-case one.

Furthermore, it's straightforward to add a data structure that would let you efficiently search for things such as "the next set bit starting with nth position in the array": just build a scan of run lengths.