Question about bit population count Algorithm

Question

POPCNT_MULT = 0x0000000000002000000000100000000008000000000400000000020000000001;
POPCNT_MASK = 0x0001041041041041041041041041041041041041041041041041041041041041;
POPCNT_MODULO = 0x3F;

number of bits turned on(1) in "num" = ((("num" * POPCNT_MULT) & POPCNT_MASK) % POPCNT_MODULO)

example :

num = 3 ( 3 = 0011 )

number of bits turned on(1) in "num" = (((3 * POPCNT_MULT) & POPCNT_MASK) % POPCNT_MODULO) = 2

---

hello! While studying algorithms, I found an algorithm with the above formula.

I want to study the above algorithm, but I don't know what the algorithm of the formula refers to...

It may be Hammingweight, but it may not be,,,

Answer 1

The first number, POPCNT_MULT, serves to repeat the initial value, concatenated bitwise. Another way of viewing it:

0x0000000000002000000000100000000008000000000400000000020000000001 = 
  (0x2000000000000000000000000000000000000000000000000000
 + 0x100000000000000000000000000000000000000000
 + 0x8000000000000000000000000000000
 + 0x400000000000000000000
 + 0x20000000000
 + 0x1)

So the last part is just 1 times the value, 0x20000000000 is just a 1 followed by a bunch of zeros in binary, so the product is going to be the same just shifted left a bunch of bits, and so on for the remaining terms. There are enough padding zeros to ensure that the terms do no overlap while adding.

The next number, POPCNT_MASK, serves mask off all but every 6th bit of the product. To see why, take the magic repeated value 0x041, and write it in binary: 000001000001. The number of zeros of padding in the previous section was also chosen such that the masking preserves each bit of the individual value in exactly one of its repeated occurrences. In a way, we've effectively fanned out the value, interleaving spans of 5 consecutive zeros, and then permuted the order of the original bits.

Finally, we take the result modulo POPCNT_MODULO. This is where the real magic happens. Since all the bits of the original number are now spread out every 6 bits, they have effectively been multiplied by various powers of 2^6, or 64. If we take the bit at the ith position in the modified value (just after masking) to be b_i, then we can express the number as:

n = (b_0 * 64^0) + (b_1 * 64^1) + (b_2 * 64^2) + ...

If we take the result modulo 0x3F, or 63, we get our final expression:

                                               n = POPCNT mod 63
(b_0 * 64^0) + (b_1 * 64^1) + (b_2 * 64^2) + ... = POPCNT mod 63

We can simplify by reducing each coefficient mod 63: 64 = 1 mod 63:

(b_0 * 1^0) + (b_1 * 1^1) + (b_2 * 1^2) + ... = POPCNT mod 63
 b_0         + b_1         + b_2        + ... = POPCNT mod 63

Its then pretty clear why this result equals the POPCOUNT of the original value- its just summing the bits, taking the result mod 63. As long as the number of set bits is less than 63 (which its guaranteed to be), the result reduced modulo 63 equals the sum of bits outright.