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.
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.