During a job interview I had some time ago I was asked to calculate the number of positive (i.e. set to "1") bits in a bitvector-structure (like unsigned integer or long). My solution was rather straightforward in C#:
int CountBits(uint input)
{
int reply = 0;
uint dirac = 1;
while(input != 0)
{
if ((input & dirac) > 0) reply++;
input &= ~dirac;
dirac<<=1;
}
return reply;
}
Then I was asked to solve the task without using without using any shifts: neither explicit (like "<<" or ">>") nor implicit (like multiplying by 2) ones. The "brute force" solution with using the potential row of 2 (like 0, 1, 2, 4, 8, 16 etc) wouldn't do either.
Does somebody know such an algorithm?
As far as I understood, it should be a sort of more or less generic algorithm which does not depend upon the size of the input bit vector. All other bitwise operations and any math functions are allowed.
There is this x & (x-1) hack that, if you give it a thought for a while, clears last 1 in an integer. Rest is trivial.