以 O(1) 计算汉明权重 [重复]

在二进制表示中，汉明权重是 1 的数量。我偶然发现了网络并找到了一个 O(1) 的答案：

v = v - ((v>>1) & 0x55555555);
v = (v & 0x33333333) + ((v>>2) & 0x33333333);
int count = ((v + (v>>4) & 0xF0F0F0F) * 0x1010101) >> 24;

但是我不太理解该算法，也无法在任何地方找到它的描述。有人可以解释一下吗，特别是最后一行（*0x1010101 然后 >> 24 到底是什么意思）？

这是用于计数位的分而治之策略的一部分，称为“填充”函数。对这一策略的学术处理可以在 Reingold 和 Nievergelt, 1977 中找到。

这个想法是首先对位进行求和，然后按 4 次求和，然后按 8 次求和，依此类推。例如，如果您有位1011，然后第一对10变成01因为有一位，第二位就变成了10因为10 = 2以二进制表示，有两个位11。这里的基本事实是：

population(x) = x - (x/2) - (x/4) - (x/8) - (x/16) - ... etc.

您拥有的确切算法是所谓的“HAKMEM”算法的变体（参见 Beeler、Gosper 和 Schroppel，1972）。这个算法算数1并行在 4 位字段中，然后将这些和转换为 8 位和。最后一步是通过乘以将这 4 个字节相加的操作0x01010101. The 0x0F0F0F0Fmask 通过屏蔽掉非和信息来获取 4 个字节的和。例如，假设 8 维字段是10110110，那么有 5 位等于0101，因此我们将有10110101。只有最后四位是有效的，因此我们屏蔽掉前四位，即：

10110101 & 0x0F = 00000101

您可以在亨利·沃伦 (Henry Warren) 所著的《黑客之乐》一书中找到有关位计数细节的完整章节。