汉明距离常数从何而来

Question

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
}

用于计算Hamming Weight。我想知道这些常量是从哪里来的，以及通常是如何发现这种方法的。想知道是否有人知道描述它的资源。

Answer 1

有屏蔽select偶数k位部分，k=1给出0x55555555，k=2给出0x33333333，k=4给出0x0f0f0f0f。

二进制掩码如下所示：

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

它们也是 0xffffffff / 3、0xffffffff / 5 和 0xffffffff / 17 的结果，但这种算术洞察力在这种情况下可能没有用。

总的来说，这种计算汉明权重的方法具有树的形式，其中首先将相邻位相加为一个 2 位数字，然后将相邻 2 位数字相加为 4 位数字，依此类推。

所有步骤都可以采用这种形式：

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

其中 m[k] 是 select 对偶数 k 位部分的掩码。

但是很多步骤都有捷径可供使用。比如相邻位求和，只需要考虑4种情况：

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

这可以通过提取两个位并将它们相加来完成，但 x -= x >> 1 & 0x55555555 也可以。这从2位部分减去最高位，所以

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

也许这可以通过 "cleverness and insight" 发现，不管它们是什么。

在步骤 x = (x + (x >> 4)) & 0x0f0f0f0f（为清楚起见添加了额外的括号）中，使用了几个属性。前面步骤的结果是4位字符串的汉明权重，每个存储4位，所以它们最多为0100。这意味着它们中的两个可以原地相加而无需进位到下一个更高的部分，因为它们的总和最多 1000 仍然适合。因此，与其在求和之前屏蔽两次，不如在求和之后屏蔽一次就足够了，这个屏蔽有效地将偶数编号的 4 位部分零扩展为 8 位部分。这可以通过考虑每一步的最大值来发现。

步骤 x += x >> 8 有类似的推理，但效果更好，甚至不需要在求和后进行屏蔽，这在从底部和顶部的第二个字节中留下了一些 "stray bits"字节，但这不会损坏下一步：>> 16 从底部扔掉第二个字节，最后所有杂散位都用 x & 0x7f.

删除

汉明距离常数从何而来

Where the Hamming Distance Constants Came From

cryptography

bit-manipulation

hamming-distance