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 .
int count =0; int no = 4; while(no!=0){ int d = no%2; if(d==1) count++; no = no/2; str = str+ d; } 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.
Use Java API(java 5 or above).
Integer.bitCount(int); Long.bitCount(long); NOTE: The above java methods are based on hacker's delight
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); } } 
no is a constant the loop can be optimized away.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.
sizeof(type)*8 say 32 for an Int32We 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; } 
OverflowException. If it were C#, it would require a checked block to get the exception.
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!
There are various ways to do this very fast.
int no =1234; int tmp =0; tmp = no - ((no >> 1) & 033333333333) - ((no >> 2) & 011111111111); System.out.println( ((tmp + (tmp >> 3)) & 030707070707) % 63); 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 
int in the code sample should have tipped you off that he's using signed integers, meaning that the magnitude check wouldn't work. Also, it should have told you that Ruby code isn't useful.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 