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: 
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](http://www.posix.nl/linuxassembly/nasmdochtml/nasmdoca.html#section-A.10).
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](http://www.jjj.de/fxt/) Details can be found in the [FXT book (pdf)](http://www.jjj.de/fxt/fxtbook.pdf), in section 1.3.2.
Sometimes people use [run-length encoding](https://en.wikipedia.org/wiki/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 `n`th position in the array": just build a [scan](https://en.wikipedia.org/wiki/Prefix_sum) of run lengths.