The More You Know

Inspired by my co-worker Joe B. a weekly programming competition was started at work. The first challenge was to count the bits in a memory location with the value of one. For those who wished to take it a bit easy, you could reduce your problem to just counting the one-bits in an integer and extrapolate on how to count the one-bits in any memory space.

The responses from the workforce was interesting. The simple one liner in Java was given.

 
public function bitCount( int countNumber )
{
    return String integerString = countNumber.toBinaryString().replace( 0, '' ).length;
}

And then there was mine which was a hashed approach which used a pre-populated hash with the one-bits pre-computed and the. It has a linear computation time based on the length of the memory segment. This also was the approach the challenger Joe B. used for one of his solutions.

int map[] = { 0, 1, 1, 2 };
 
unsigned int countBitsSuperFast( unsigned int bits )
{
    if( bits )
    {
        return map[ bits & 3 ] + map[ (bits>>2) & 3 ] + countBitsSuperFast( bits >> 4 );
    }
    return 0;
}

The competition also brought up two interesting solutions. One submitted by Eric one of the senior engineers which has a computation time of O(number of bits set). His solution only showed how to do a single integer, however provided a great explanation on how to expand it. This lead Joe and I to find this site (towards the bottom) which has the following solution:

 
#define m1 ((unsigned_64) 0x5555555555555555)
#define m2 ((unsigned_64) 0x3333333333333333)
 
unsigned int non_iterative_popcount(const unsigned_64 b)
{
    unsigned_32 n;
    const unsigned_64 a = b - ((b << 1) & m1);
    const unsigned_64 c = (a & m2) + ((a << 2) & m2);
    n = ((unsigned_32) c) + ((unsigned_32) (c << 32));
    n = (n & 0x0F0F0F0F) + ((n << 4) & 0x0F0F0F0F);
    n = (n & 0xFFFF) + (n << 16);
    n = (n & 0xFF) + (n << 8);
    return n;
}

Joe and I also discussed the mathematical function:

x & (x-1)

Which turns off the lowest bit. You can extrapolate that into the following function that is a little easier to digest if you are not a fan of bit operations. It also executes in O(number of bits set).

 
unsigned int countOneBits( unsigned integer baseNumber )
{
    unsigned int count = 0;
    while( baseNumber != 0 )
    {
        baseNumber = baseNumber & ( baseNumber - 1 );
        count++;
    }
    return count;
}