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

Question

During the interview I had some time ago I was asked to calculate the number of positive (that is, set "1") bits in the structure of the bitvector (for example, an unsigned integer or long). My solution was pretty simple 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 problem without use without any shifts: neither explicit (for example, "<" or "→"), nor implicit (for example, multiplying by 2). The brute force solution using potential row 2 (for example, 0, 1, 2, 4, 8, 16, etc.) will not be the same.

Does anyone know such an algorithm?

As I understand it, this should be a kind of more or less general algorithm that does not depend on the size of the input bit vector. All other bitwise operations and any mathematical functions are allowed.

Answer 1

There is this x & (x-1) hack which, if you think a little, clears the last 1 in integer size. Rest is trivial.

Answer 2

Some processors have instructions for counting numbers. If not, I believe this is the fastest method (for 32-bit):

 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

Regarding this 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]; } 

Answer 3

Just as Anthony Blake described, but a little more readable, I think.

 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; }