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