counting number of ones in binary representation of a number

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

Use Java API(java 5 or above).

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

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

Answer 2

faster than any of the earlier answers: (proportional to number of 1 bits rather than total bits)

public class Foo {
  public static void main(String[] argv) throws Exception {
    int no = 12345;
    int count;
    for (count = 0; no > 0; ++count) {
      no &= no - 1;
    }
    System.out.println(count);
  }
}

Answer 3

Looks like c/c++/c#, if so you have shifting.. just loop to N-1 bits from 0 and use sum+=(value>>i)&1

Ie: you always check the last/right most bit but move the binary representation of the number to the right for every iteration until you have no more bits to check.

Also, think about signed/unsigned and any integer format. But you dont state how that should be handled in the question.

Answer 4

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 5

One idea that's commonly employed for counting ones is to build a lookup table containing the answers for each individual byte, then to split apart your number into four bytes and sum the totals up. This requires four lookups and is quite fast. You can build this table by writing a program that manually computes the answer (perhaps using your above program), and then can write a function like this:

private static final int[] BYTE_TOTALS = /* ... generate this ... */;

public static int countOneBits(int value) {
    return BYTE_TOTALS[value        & 0xFF] +
           BYTE_TOTALS[value >>>  8 & 0xFF] +
           BYTE_TOTALS[value >>> 16 & 0xFF] +
           BYTE_TOTALS[value >>> 24 & 0xFF];
}

Hope this helps!

Answer 6

There are various ways to do this very fast.

MIT HAKMEM Count

int no =1234;
int tmp =0;
tmp = no - ((no >> 1) & 033333333333) - ((no >> 2) & 011111111111);
System.out.println( ((tmp + (tmp >> 3)) & 030707070707) % 63);

Answer 7

Your end condition should be keeping track of the magnitude of the bit you are at; if it is larger than the original number you are done (will get only 0s from now on).

Oh, and since you didn't specify a language, here's a Ruby solution :)

class Integer
  def count_binary_ones
    to_s(2).scan('1').length
  end
end

42.count_binary_ones #=> 3

Answer 8

How about using the BigInteger class.

public void function(int checkedNumber) {
    BigInteger val = new BigInteger(String.valueOf(checkedNumber));
    val = val.abs();
    int count = val.bitCount();
    String binaryString = val.toString(2);

    System.out.println("count = " + count);
    System.out.println("bin = " + binaryString);
}

The result of function(42); is following.

count = 3
bin = 101010