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.
There is a way to do it in near O(k) time [plus O(n/64)] using the c++ standard bit manipulation tools in C++20.  

The O(n/64) is not a problem for me, but is may be an issue if you set is very large and very sparse.  

These map to CPU intrinsics on all the major platforms (x64, ARM, etc).

On order for this to work we have to make a few assumptions.

1: The bitset is a standard size linked with the native register size. 64 bits is a good starting point. You store the bitsets in an array as shown below.

2: The number of set bits is known, or the length of the bitset is known.
You could add length checking to the function, but this code assumes you know the number of set bits in advance (because you are tracking them in some additional list).

```
//Walk through an array of std::bitset<64>
//And return the index of the next set bit.
//No attempt is made to stay within the bounds of the array
//So you need to know how many bits are set in total.
template <bool satbit>
int NextSetBit(const std::bitset<64>* bits, const int previous = -1) {
    //walking through the satisfied bits of a bitset using tzcnt is much faster than testing each single bit
    //esp for bitset that have many 0 bits.
    assert(nullptr != bits);
    assert(previous >= -1);
    //get followup bits
    auto next = previous + 1;
    auto chunk = (next / 64); //starting chunk
    const auto firstmask = uint64_t(-1) << (next % 64); //mask off the previously investigated bits
    const auto getnextchunk = [=](const int chunk) { 
        if constexpr (satbit) { return   bits[chunk].to_ullong(); }
        else                  { return ~(bits[chunk].to_ullong()); }
    };
    auto data = firstmask & getnextchunk(chunk);
    while (0 == data) { 
        data = getnextchunk(++chunk);
    }
    next = std::countr_zero(data);
    assert(bits[chunk].test(next) == satlit);
    return (next + (chunk * 64));
}

```

The code is called as follows:

```
const auto length = LengthOf(bits);
auto next = -1;
for (auto i = 0; i < SetBitCount; i++) {
    next = NextSetBit<true>(bits, next);
    assert(next < length);
    doStuff(next);
}

```

The n/64 overhead factor is only a problem if your set is very sparse. You can fix this by excluding empty chunks from the iteration, using a list that tracks chunks that have set bits in them. Such bookkeeping can easily be made O(1).  

You are thus able to avoid empty chunks, making the code truly O(k) at the cost of some constant overhead.

Because such a registration needs to track the number of set bits per chunk anyway, you can use the code as is without having to add bounds checking.