Counting No of ones in the binary representation of a number.

Approach 1:
Lets say the number is n. If you do n&(n-1) it will change the rightmost one in the number to zero.
int i = n?1:0;
while(n = (n & (n-1))) i++;


Approach 2:
If we are given little more memory, we can keep an array of 256 elements, value of each element being the no of ones in the index. for ex. table[0] = 0; table[1] = 1; table[2] = 1; table[3] = 2; etc.

So no of ones in a 4 byte integer n will be,
no_of_ones = table[n&0xff] + table[(n>>8)&0xff] + table[(n>>16)&0xff] + table[(n>>24)&0xff];

Approach 3:
lets say x is another no whose binary representation is 01010101.(or of this pattern)
now if we perform the operation
n = n&x + (n>>1)&x;
Now each 2 bits block in n 'll give no of ones presented in that block in the initial value of n.For ex.
00 --> there was no 1 in these two bit positions.
01 --> there was only one 1 in these two bit positions(irrespective of the place of that 1).
10 -->both of these positions were having 1.
lets take an example (...do the home work).

Now lets say y is another no whose binary representation is 00110011.
perform the same operation
n = n&y + (n>>2)&y;
similarly if we look at four bits blocks in n, each block 'll give no of ones presented in that block in the initial value of n. For example 0010 -> there were two 1s in this block.

so keep doing this until you get the size of one block equal to size of the number given.
For a 4 byte integer(n) no of ones are m
m = (n & 0x55555555) + ((n>>1)&0x55555555); [0x55555555 - >32 bit no of 01010101.. pattern]
m = (m & 0x33333333) + ((m>>2) &0x33333333); [u know where from i got 0x33333333]
m = (m &0x0f0f0f0f) + ((m>>4) & 0x0f0f0f0f); [same logic goes on]
m = (m &0x00ff00ff) + ((m>>8) & 0x00ff00ff);
m = (m & 0x0000ffff) + ((m>>16) & 0000ffff);

now m is the no of ones present in the given number.
So for a number having size 2^x bytes, x+3 steps are needed.
Note: It just counts the number of ones in the binary representation, for signed integers the binary representation is machine dependent. For ex -1 in two's compliment form written as all ones.