在二进制表示中，汉明权重是 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 位，依此类推。例如，如果你有 bits 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。掩码通过0x0F0F0F0F屏蔽非总和信息来获得 4 位字节总和。例如，假设 8 位字段是10110110，那么有 5 位等于0101，因此我们将有10110101。只有最后四位是有效的，所以我们屏蔽了前四位，即：
10110101 & 0x0F = 00000101
您可以在亨利·沃伦 (Henry Warren) 所著的《黑客的喜悦》(Hacker's Delight) 一书中找到有关计数细节的一整章。