How to calculate the number of positive bits without using any shifts?

Question

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.

Louque

"All other bitwise operations and any math functions are allowed" but presumably, addition is only allowed if it is not used to implement the multiplication by two that's equivalent to a bit shift. These interview questions are stupid, no offense to you. – Wommera

Great resource for you gurmeet.net/puzzles/fast-bit-counting-routines – Petroleum

Yes, it had to be a different approach, not re-implementing what I already had just with a different flavor. Thank you for making it more precise! – Louque

See #1611833 (amongst others), which links to graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive – Moidore

Answer 1

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.

Ventriloquist

Did you read it somewhere or you found it first on your own? Is it imaginable to come up with such a solution spontaneously during a job interview? Anyway, +1 and thumbs up! – Louque

@AlexanderGalkin it is, if the interviewee knows how computers work, but it's also a well-known trick .. more of a technique maybe, it's frequently useful not just to count bits. – Selfhelp

@harold: Hmm, what area is this trick well known in? I used to program a lot in Assembler and read many resources devoted to bitwise operations -- and actually I have definitely seen it for even during the interview it already "rang a bell". But I could not remember or derive it quickly under stressful conditions during the interview. – Louque

@AlexanderGalkin: On my own, I think. I cannot remember for sure. Maybe I have seen it implemented in an assembler instructions and only then analyzed what that strange operation does... it was long ago. – Ventriloquist

@AlexanderGalkin stress kills thought more efficiently than alcohol :) The trick is frequently used when treating integers as bitsets (also often pops up in graph algorithms on bitmatrices), when testing whether something is a power of 2 (could be called counting with an early exit), and as part of other bithacks. – Selfhelp

Actually using of BSF x86 instruction with shift might give the same speed. Actually it works good for sparse bits set to 1, but might be not so fast for situation when all bits is set. – Clothespress

Answer 2

Some processors have a population count instruction. If not, I believe this is the fastest method (for 32-bits):

int NumberOfSetBits(int i) {
  i = i - ((i >> 1) & 0x55555555);
  i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
  return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

See this link for a full explanation: http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel

As for doing it without shifts, I think using a lookup table would be the best answer:

int NumberOfSetBits(int i) {
  unsigned char * p = (unsigned char *) &i;
  return BitsSetTable256[p[0]] + BitsSetTable256[p[1]] + 
     BitsSetTable256[p[2]] + BitsSetTable256[p[3]];
}

// To initially generate the table algorithmically:
BitsSetTable256[0] = 0;
for (int i = 0; i < 256; i++) {
  BitsSetTable256[i] = (i & 1) + BitsSetTable256[i / 2];
}

Haematozoon

this solution has 4 shifts in it – Clypeate

Interesting. It looks crazy, but maybe it actually works. But the question was "no shifts". Also, it is specialized for the specific number of bits, the question for "integer or long" which for me means, potentially any bit-length stored in single variable. – Ventriloquist

See above for the lookup table method -- sorry, was getting to that part =) – Haematozoon

Taking away shift operation as for me is synthetic restriction. If you just don't have them - just use multiplications. I like idea of folding bits with sum operation over the binary tree, but this solution looks a bit different. – Clothespress

btw. I think interviewer wanted answer with lookup table, rather than those bits juggling things. – Clothespress

Answer 3

In the same way as Anthony Blake described, but a bit more readable, I guess.

uint32_t bitsum(uint32_t x)
{
    // leafs (0101 vs 1010)
    x = (x & 0x55555555) + ((x >> 1) & 0x55555555);

    // 2nd level (0011 vs 1100)
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);

    // 3rd level (nybbles)
    //x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
    x = (x & 0x07070707) + ((x >> 4) & 0x07070707);

    /*
    // 4th level (bytes)
    //x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);
    x = (x & 0x000f000f) + ((x >> 8) & 0x000f000f);

    // 5th level (16bit words)
    //return (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff);
    return (x & 0x0000001f) + ((x >> 16) & 0x0000001f);
    */
    // since current mask of bits 0x0f0f0f0f
    // result of summing 0f + 0f = 1f
    // x * 0x01010101 will produce
    // sum of all current and lower octets in
    // each octet
    return (x * 0x01010101) >> 24;
}

Clothespress