C++: building iterator from bits

Question

I have a bitmap and would like to return an iterator of positions of set bits. Right now I just walk the whole bitmap and if bit is set, then I provide next position. I believe this could be done more effectively: for example build statically array for each combination of bits in single byte and return vector of positions. This can't be done for a whole int, because array would be too big. But maybe there are some better solutions? Do you know any smart algorithms for this?

Answer 1

I can suggest several ideas.

• Turns out modern CPUs have dedicated instructions for finding the next set bit in a 32- or 64-bit word.
• I like very much your idea of constructing the iterator for the whole bitmap from prepared efficient per-byte mini-iterators, this is really cool and I'm surprised I've never seen it before!
• If your bitmap is very sparse, you may represent it in some other form, such as a balanced tree, where iteration algorithms are quite well-known.
• If your bitmap is sparse but with dense regions (that sounds exotic, but I've encountered situations where this was exactly the case), use a balanced tree of small (32-bit or 64-bit) bitmaps and use a combined iteration algorithm for a tree and for bits of a word.
• To avoid the memory overhead of an explicit tree, use an implicit one, like in the canonical heapsort algorithm. After your bitset is ready and will not be mutated, build a "pyramid" on top of it where level(N+1)[i] = level(N)[2*i] | level(N)[2*i+1]. This will allow you to rapidly skip uninhabited regions of the bitset, and iteration will be done in a fashion similar to iterating over a regular binary tree. You might as well build a pyramid of inhabitance, starting from bytes, etc.: it all depends on how sparse your bitset it.
• There are well-known bit tricks for finding the number of leading zeros in a word; see, for example, the code of java's standard libraries:
• You might gain a lot of performance by using a passive iterator instead of an active one, t.i. instead of begin() and operator++(), provide a foreach(F) function for your bitset where F has operator(). If you need passive iteration with premature termination, make F's operator() return a boolean that denotes whether termination is requested.

EDIT: I couldn't resist trying out your approach with preparing iterators for bytes. I wrote a code generator into C#2.0 that produces code of the following form:

IEnumerable<int> bits(byte[] bytes) {
    for(int i=0; i<bytes.Length; ++i) {
        int oi=8*i;
        switch(bytes[i]) {
            ....
            case 74: yield return oi+1; yield return oi+4; yield return oi+6; break;
            ....
        }
    }
}

I compared its performance for counting bits of a random 50%-filled byte array (10Mb) with the performance of code that does not use iterators at all and consists of two loops:

for (int i = 0; i < bytes.Length; ++i) {
    byte b = bytes[i];
    for (int j = 7; j >= 0; --j) {
        if (((int)b & (1 << j)) != 0) s++;
    }
}

The second code snippet is just some 1.66 times faster than the first one (~1.5s vs ~2.5s). I think that sparser bit arrays might even make the first code outperform the second one.