6

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.

Svante
  • 50,694
  • 11
  • 78
  • 122
Alexander Galkin
  • 12,086
  • 12
  • 63
  • 115
  • 1
    "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. – Pascal Cuoq Nov 20 '11 at 10:49
  • Great resource for you http://gurmeet.net/puzzles/fast-bit-counting-routines/ – zaf Nov 20 '11 at 10:51
  • 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! – Alexander Galkin Nov 20 '11 at 10:53
  • See http://stackoverflow.com/questions/1611333/how-many-1s-in-an-n-bit-integer (amongst others), which links to http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive – Matthew Strawbridge Nov 20 '11 at 10:56

3 Answers3

13

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.

  • 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! – Alexander Galkin Nov 20 '11 at 11:52
  • @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. – harold Nov 20 '11 at 12:11
  • @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. – Alexander Galkin Nov 20 '11 at 12:15
  • @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. –  Nov 20 '11 at 12:27
  • @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. – harold Nov 20 '11 at 12:41
  • 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. – ony Nov 20 '11 at 13:59
1

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];
}
Anthony Blake
  • 5,328
  • 2
  • 25
  • 24
  • this solution has 4 shifts in it – flolo Nov 20 '11 at 10:56
  • 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. –  Nov 20 '11 at 10:56
  • See above for the lookup table method -- sorry, was getting to that part =) – Anthony Blake Nov 20 '11 at 10:57
  • 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. – ony Nov 20 '11 at 14:03
  • btw. I think interviewer wanted answer with lookup table, rather than those bits juggling things. – ony Nov 20 '11 at 15:30
1

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;
}
ony
  • 12,457
  • 1
  • 33
  • 41