Not necessarily a C program (though I'm pretty sure it works in C too). int count_set(int n){ int count=0; //counts the bits while(n!=0){ count++; n=n&(n-1);//clear out the most significant set bit } return count; } This goes through exactly the number of iterations as the number of set bits in n. In the worst case however, it still goes through the loop O(logn) times (there are logn bits in an integer n). Another option, if you have infinite memory, you can create a lookup table containing the number of bits in, say, a nibble (4-bit hex numbers 0 to D). Can increase or decrease this lookup table (8 bit numbers, 12 bit numbers, even something that's not a multiple of 4). Of course, if you have infinite memory, you can create a lookup table that's 2^32 entries long, but that's roughly a billion... I'm assuming something similar could be done in C (if not identical). The 0x prefix refers to a hex number in Java. int count_setTable(int n){ int number=0;//counts set bits int [] count={0,1,1,2, //number of 1s in binary of 0,1,2,3,... 1,2,2,3, // 4,5,6,7,... 1,2,2,3, 2,3,3,4} //.. ...15. //if you use 8 bits, your entries will be number of 1s in binary representation of 0...63 int mask = 0xF; //28 zeros followed by four 1s in hex, basically the number 15 in int //if you use, 8 bits, you could use either 0xFF or 255 //there are 32 bits in an int, so 8 groups of 4 bits for(int i=0; i>4;//shift the bits of n out (would need to shift the copy in if checking against 0) } return number; } Other methods count the set bits one-by-one, ANDing with 1 or 0x80000000 while n!=0 and increasing the count if this AND != 0, and then shifting n 1 position to the right (logical shift) or to the left, respectively.