I've had this sitting in my drafts for a while, the other bitset thread inspired me to post it. Decided to make a new thread to avoid derailing the other one.

I think it would be nice if std::bitset had a way to find the first/next set bit.

MOTIVATION

I recently sped up some code quite a lot. It had a container of optional work items. I changed to using a separate std::bitset to mark whether each element contained a valid work item. Something like this:

some_container_smaller_than_65  work_items;
std::bitset<64>  valid;

When looking for a valid work item, one can simply pick the first set bit in the "valid" bitset. This can be done very efficiently with e.g. the tzcnt instruction on x86, or rbit+clz on ARM.

Similarly, one can also very efficiently (with an extra instruction or two) find the next set bit after a given index, making it possible to efficiently iterate over the set bits.

(In my case, we also had "ready" and "done" bitsets, so it took only a few instructions to find the first/next work item that was valid and ready but not done.)

EXISTING IMPLEMENTATIONS