Where the Hamming Distance Constants Came From

Question

The function:

function popcount (x, n) {
  if (n !== undefined) {
    x &= (1 << n) - 1
  }

  x -= x >> 1 & 0x55555555
  x = (x & 0x33333333) + (x >> 2 & 0x33333333)
  x = x + (x >> 4) & 0x0f0f0f0f
  x += x >> 8
  x += x >> 16

  return x & 0x7f
}

Is for calculating Hamming Weight. I am wondering where these constants come from and generally how this method was discovered. Wondering if anyone knows the resource that describes it.

Answer 1

There masks select the even numbered k-bit parts, k=1 gives 0x55555555, k=2 gives 0x33333333, k=4 gives 0x0f0f0f0f.

In binary the masks look like:

0x55555555 = 01010101010101010101010101010101
0x33333333 = 00110011001100110011001100110011
0x0f0f0f0f = 00001111000011110000111100001111

They are also the result of 0xffffffff / 3, 0xffffffff / 5 and 0xffffffff / 17 but this arithmetic insight is probably not useful in this context.

Overall this method of computing the Hamming weight has the form of a tree where first adjacent bits are summed into a 2-bit number, then adjacent 2-bit numbers are summed into 4-bit numbers, and so on.

All the steps could have this form:

x = (x & m[k]) + ((x >> k) & m[k])

where m[k] is a mask selecting the even-numbered k-bit parts.

But many steps have short-cuts available for them. For example, to sum adjacent bits, there are only 4 cases to consider:

00 -> 00
01 -> 01
10 -> 01
11 -> 10

This could be done by extracting both bits and summing them, but x -= x >> 1 & 0x55555555 also works. This subtracts the top bit from the 2-bit part, so

00 -> 00 - 0 = 00
01 -> 01 - 0 = 01
10 -> 10 - 1 = 01
11 -> 11 - 1 = 10

Maybe this could be discovered through "cleverness and insight", whatever those are.

In the step x = (x + (x >> 4)) & 0x0f0f0f0f (extra parentheses added for clarity), a couple of properties are used. The results from the previous steps are the Hamming weights of 4-bit strings stored in 4 bits each, so they are at most 0100. That means two of them can be added in-place without carrying into the next higher part, because their sum will be at most 1000 which still fits. So instead of masking twice before the sum, it is enough to mask once after the sum, this mask effectively zero-extends the even numbered 4-bit parts into 8-bit parts. This could be discovered by considering the maximum values at each step.

The step x += x >> 8 has similar reasoning but it works out even better, even masking after the sum is not needed, this leaves some "stray bits" in the second byte from the bottom and in the top byte, but that is not damaging to the next step: the >> 16 throws away the second byte from the bottom, in the end all the stray bits are removed with x & 0x7f.