Bit count

Problem:
Given a number, count the number of bits set in that number. There are 2 methods represented below.
First solution does the calculation in constant time, but it assumes it is a 32-bit machine.
Second solution doesnot assume anything such that and it works for both 32 & 64-bit machine. But the runtime of that machine is O(M) where M is the number of bit set in that number.

Soultion:

#include <iostream.h>
using namespace std;

typedef unsigned long long uint64;  //assume this gives 64-bits
unsigned long m1  = 0x5555555; //binary: 0101...
const uint64 m2  = 0x33333333; //binary: 00110011..
const uint64 m4  = 0x0f0f0f0f; //binary:  4 zeros,  4 ones ...
const uint64 m8  = 0x00ff00ff; //binary:  8 zeros,  8 ones ...
const uint64 m16 = 0x0000ffff; //binary: 16 zeros, 16 ones ...
const uint64 hff = 0xffffffff; //binary: all ones
const uint64 h01 = 0x01010101; //the sum of 256 to the power of 0,1,2,3...

//This is a naive implementation, shown for comparison,
//and to help in understanding the better functions.
//It uses 24 arithmetic operations (shift, add, and).
int popcount_1(uint64 x) {
    x = (x & m1 ) + ((x >>  1) & m1 ); //put count of each  2 bits into those  2 bits
    x = (x & m2 ) + ((x >>  2) & m2 ); //put count of each  4 bits into those  4 bits
    x = (x & m4 ) + ((x >>  4) & m4 ); //put count of each  8 bits into those  8 bits
    x = (x & m8 ) + ((x >>   & m8 ); //put count of each 16 bits into those 16 bits
    x = (x & m16) + ((x >> 16) & m16); //put count of each 32 bits into those 32 bits
    return x;
}

int countNaive(int number)
{
    int count = 0;
    while(number)
    {
        count++;
        number = number & (number -1);
    }

    return count;
}
int main()
{
    cout<<"Enter the number: ";
    int number;
    cin>>number;
    cout<<"Number of bits: "<<popcount_1(number)<<endl;
    cout<<"Number of bits(Naive Method): "<<countNaive(number)<<endl;
    return 0;
}

~ by Ganesh on January 8, 2009.