Count number of 1's in binary representation

Efficient way to count number of 1s in the binary representation of a number in O(1) if you have enough memory to play with. This is an interview question I found on an online forum, but it had no answer. Can somebody suggest something, I cant think of a way to do it in O(1) time?

Solution 1:

That's the Hamming weight problem, a.k.a. population count. The link mentions efficient implementations. Quoting:

With unlimited memory, we could simply create a large lookup table of the Hamming weight of every 64 bit integer

Solution 2:

I've got a solution that counts the bits in O(Number of 1's) time:

bitcount(n):
    count = 0
    while n > 0:
        count = count + 1
        n = n & (n-1)
    return count

In worst case (when the number is 2^n - 1, all 1's in binary) it will check every bit.

Edit: Just found a very nice constant-time, constant memory algorithm for bitcount. Here it is, written in C:

int BitCount(unsigned int u)
{
     unsigned int uCount;

     uCount = u - ((u >> 1) & 033333333333) - ((u >> 2) & 011111111111);
     return ((uCount + (uCount >> 3)) & 030707070707) % 63;
}

You can find proof of its correctness here.

Solution 3:

Please note the fact that: n&(n-1) always eliminates the least significant 1.

Hence we can write the code for calculating the number of 1's as follows:

count=0;
while(n!=0){
  n = n&(n-1);
  count++;
}
cout<<"Number of 1's in n is: "<<count;

The complexity of the program would be: number of 1's in n (which is constantly < 32).

Solution 4:

I saw the following solution from another website:

int count_one(int x){
    x = (x & (0x55555555)) + ((x >> 1) & (0x55555555));
    x = (x & (0x33333333)) + ((x >> 2) & (0x33333333));
    x = (x & (0x0f0f0f0f)) + ((x >> 4) & (0x0f0f0f0f));
    x = (x & (0x00ff00ff)) + ((x >> 8) & (0x00ff00ff));
    x = (x & (0x0000ffff)) + ((x >> 16) & (0x0000ffff));
    return x;
}

Solution 5:

public static void main(String[] args) {

    int a = 3;
    int orig = a;
    int count = 0;
    while(a>0)
    {
        a = a >> 1 << 1;
        if(orig-a==1)
            count++;
        orig = a >> 1;
        a = orig;
    }

    System.out.println("Number of 1s are: "+count);
}