Count number of 1's in binary representation

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

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.

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).