Bitwise iterator. Interested?

From: Borgerding, Mark A. (MarkAB_at_[hidden])
Date: 2000-06-07 12:56:27

I would like to find out if there is sufficient interest for a class that
acts upon a block of raw data like a random-access iterator to bits.  The
iterator dereferences to a proxy object that reads/writes a given bit in a
byte.

I have previously created a version of this class on my employer's time.  I
respect that and will not copy it.  However, if there is sufficient
interest, I can recreate the class on my own time under a boost-compatible
license.

The impetus for this class was the need for an efficient ( both space and
time ) way of handling variable or irregular bit-length codes without
needing to copy the data into/out of a container.

The use of bit_iterator has lead to much cleaner looking code in the area of
bitwise manipulation. The code is as efficient as any general purpose(#1)
get/set bit macros or functions.  I compared its efficiency at flipping bits
with that of Dinkumware's specialized vector<_Bool, _Bool_allocator> and
found it to be over 5 times faster.  Add to that the efficiency gains from
not needing to copy buffers around, and you will start to appreciate its
usefulness.

To give you and idea of what the usage looks like, here is a silly code
sample that counts the number of set bits in a block of memory, and zeroes
out the memory (pretty inefficiently in this example).

int CountSetBits(void * pMem, size_t numBytes )
{
        int setbits=0;
        
        // construct with void*, ( optional bit offset defaults to zero)
        bit_iterator bitItBeg(pMem);

        // operator+ and copy contructor, assumes 8 bits/byte
        bit_iterator bitItEnd(bitItBeg + (8 * numBytes) );

        for ( ;
                bitItBeg != bitItEnd ; // comparison operator
                ++bitItBeg ) // increment to next bit
        {
                if ( *bitItBeg ) { // deref returns a proxy, which is
convertible to bool
                        ++setbits;
                        *bitItBeg = false;// deref returns a proxy, which is
assignable from bool
                }
        }
        cout << "Out of " << (8*NUM_BYTES) << " bits, " << setbits << " were
set.\n";
        return setbits;
}

Mark Borgerding 
markab (at) xetron . com
Software Engineer
Xetron Corporation

(footnote #1)  It may be possible to create more efficient algorthms for
specialized purposes. For example of efficient ways to count bits in a given
block of data, see the bit counters at
http://remus.rutgers.edu/~%72%68%6fad%73/Code/code.html 
All of the bit counting methods listed on that page are within one order of
magnitude of efficiency of the general purpose bit_iterator method.