Search code examples
c++bitcount

count number of set bits in integer

i am studing different methods about bit counting ,or population count methods fopr given integer, during this days,i was trying to figure out how following algorithms works

pop(x)=-sum(x<<i)   where i=0:31

i think that after calculate each value of x,we will get 

x+2*x+4*x+8*x+16*x+..............+2^31*x  =4294967294*x

if we multiply it by -1,we get -4294967294*x,but how it counts number of bits?please help me to understand this method well.thanks

Solution

  • I believe you mean

    $$\mathrm{pop}(x) = -\sum_{i=0}^{31} (x \overset{\mathrm{rot}}{\ll} i)$$

    as seen in the cover of the book Hacker's Delight, where the symbol means left-rotation not left-shift which will produce the wrong results and downvotes.

    This method works because the rotation will cause all binary digits of x to appear in every possible bits in all terms, and because of 2's complement.

    Take a simpler example. Consider numbers with only 4 binary digits, where the digits can be represented as ABCD, then the summation means:

      ABCD  // x <<rot 0
+ BCDA  // x <<rot 1
+ CDAB  // x <<rot 2
+ DABC  // x <<rot 3

    We note that every column has all of A, B, C, D. Now, ABCD actually means "2³ A + 2² B + 2¹ C + 2⁰ D", so the summation is just:

      2³ A        + 2² B        + 2¹ C        + 2⁰ D
+ 2³ B        + 2² C        + 2¹ D        + 2⁰ A
+ 2³ C        + 2² D        + 2¹ A        + 2⁰ B
+ 2³ D        + 2² A        + 2¹ B        + 2⁰ C
——————————————————————————————————————————————————————
= 2³(A+B+C+D) + 2²(B+C+D+A) + 2¹(C+D+A+B) + 2⁰(D+A+B+C)
= (2³ + 2² + 2¹ + 2⁰) × (A + B + C + D)

    The (A + B + C + D) is the population count of x and (2³ + 2² + 2¹ + 2⁰) = 0b1111 is -1 in 2's complement, so the summation is the negative of the population count.

    The argument can be easily extended to 32-bit numbers.