Counting the number of units in binary representation of a number

Question

Possible duplicate:
Best algorithm for counting the number of bits in a 32-bit integer?

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

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

• Now the second logic is to continue masking the number iteratively from 1,2,4,8,32 and check if the result is 1,2,4, 8 ..... It doesn’t work out that the condition for this cycle should end .

Answer 1

Use Java API (java 5 or higher).

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

NOTE. The above java methods are based on hacker east

Answer 2

faster than any of the previous answers: (proportional to the number of 1 bits, not the 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

Similar to c / C ++ / C #, if so, you change ... just go to N-1 bits from 0 and use sum+=(value>>i)&1

Those. you always check the last bit / right bit, but move the binary representation of the number to the right for each iteration until you have more bits to check.

Also think about signed / unsigned and any integer format. But you do not indicate how this should be considered in the question.

Answer 4

One idea that is commonly used for counting is to build a lookup table containing answers for each individual byte, then divide your number into four bytes and summarize the totals. This requires four searches and is pretty fast. You can create this table by writing a program that manually calculates the answer (possibly using the program above), 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 5

We can use 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 6

There are various ways to do this very quickly.

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 final state should track the size of the bits you are on; if it is larger than the original number you made (from now on you will only get 0).

Oh, and since you did not specify a language, here is the 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); follows.

 count = 3 bin = 101010