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: 
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, there are specialized data structures like [van Emde Boas trees](http://en.wikipedia.org/wiki/Van_Emde_Boas_tree) and [y-fast tries](http://web.stanford.edu/class/archive/cs/cs166/cs166.1196/lectures/15/Slides15.pdf), that support 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.
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.