counting number of ones in binary representation of a number [duplicate]

Question

Possible Duplicate:
Best algorithm to count the number of set bits in a 32-bit integer?

I want to find out how many 1s are there in binary representation of a number.I have 2 logic .

1.   int count =0;
   int no = 4;
   
   while(no!=0){
       int d = no%2;
       if(d==1)
           count++;
       no = no/2;
       str = str+ d;
   }
   

2. Now second logic is to keep on masking number iteratively with 1,2,4,8,32 and check if result is 1,2,4, 8..... Am not geting what should be ending condition for this loop.

Answer 1

We can make use of overflow for your loop:

int count = 0;
int number = 37;
int mask = 1;

while(mask!=0)
{
    int d = number & mask;
    if(d != 0)
        count++;
    /* Double mask until we overflow, which will result in mask = 0... */
    mask = mask << 1;
    str = str+ d;
}

Answer 2

Use Java API(java 5 or above).

Integer.bitCount(int);
Long.bitCount(long);

NOTE: The above java methods are based on hacker's delight