CareerCup

to count the number of bits in O(1), you need preprocessing, i.e., build a lookup table for 0, 127. For example lookupt[0] = 0; lookupt[1] = 1; lookupt[2] = 1; lookupt[3] = 2; ...

Given a 32-bit number, you get the number of bits,
unsigned int MASK = 0xFF;
return (lookupt[num & MASK] + lookupt[num >> 8 & MASK] + lookupt[num >> 16 & MASK] + lookup[num >> 24 & MAKS];

"improving" your algo to count the number of bits in O(1) could be a trick question. The most straightforward algorithm that simply goes through the integer bit by bit (shift left the mask, AND it with the number) is already O(1). The reason for this is that it's asymptotically bound by a constant function f(n) = sizeof(int)*8

/**
* Returns the number of bits set in val.
* For a derivation of this algorithm, see
* "Algorithms and data structures with applications to
* graphics and geometry", by Jurg Nievergelt and Klaus Hinrichs,
* Prentice Hall, 1993.
*/
private static int bitCount(long val) {
val -= (val & 0xaaaaaaaaaaaaaaaaL) >>> 1;
val = (val & 0x3333333333333333L) + ((val >>> 2) & 0x3333333333333333L);
val = (val + (val >>> 4)) & 0x0f0f0f0f0f0f0f0fL;
val += val >>> 8;
val += val >>> 16;
return ((int)(val) + (int)(val >>> 32)) & 0xff;
}

which is O(lg n)

just take log base 2 of the number floor it and add 1.

This is a very old Question check this link out the stanford site (google Bit Twiddling Hacks)

O(1)....go for Hashmap

O(1) is a constant time. So a for loop bit by bit is also O(1). But the constant factor can be optimized by using other tricks. HashMap can have the best perf but lot of space requirements. refer to (http)gurmeetsingh.wordpress.com/2008/08/05/fast-bit-counting-routines/ for some fast pieces....

if((n & n-1) == 0){
      return (int)log2(n)+1;
}
return (int)log2(n)