CareerCup

To be very frank I dont know the answer, but what I know is Java has Integer class which has a method bitcount which does the same thing in O(1).
This is the extract from the Java source code

i = i - ((i >>> 1) & 0x55555555);
1085 i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
1086 i = (i + (i >>> 4)) & 0x0f0f0f0f;
1087 i = i + (i >>> 8);
1088 i = i + (i >>> 16);
1089 return i & 0x3f;

Can someone please explain the logic?

Sorry for incorrect C/P

i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;

integer is 2/4 bytes. therefore it takes a constant steps. Does it fits the definition of O(1) ?

Use map for each byte.

google MIT HAKMEM. But I wonder why adobe keeps asking these types of questions!It can never test the intelligence. If a person knows it he will tell it, or he wont able to tell it. If one can design this algo in half an hour he probably shouldnt be at adobe ;)

int BitCount(unsigned int u)
{
unsigned int uCount;

uCount = u
- ((u >> 1) & 033333333333)
- ((u >> 2) & 011111111111);
return
((uCount + (uCount >> 3))
& 030707070707) % 63;
}

I was asked the same question in Juniper. The Answer is "Look-up table"

int c;
Int N;
for(c=0;N;c++)
{
N&=N-1;
}
printf("No of set bit=%d\n",c);