algorithm - 在O(1)中计算汉明重量

This question already has an answer here:

Number of bits set in a number

(1个答案)


7年前关闭。




用二进制表示，汉明权重是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年)。该算法并行计算4位字段中的1，然后将这些和转换为8位和。最后一步是通过乘以0x01010101将这4个字节相加的操作。 0x0F0F0F0F掩码通过屏蔽非和信息来获取4位字节的和。例如，假设8维字段是10110110，那么有5位等于0101，因此我们将得到10110101。只有后四位有效，因此我们屏蔽了前四位，即:

10110101 & 0x0F = 00000101

您可以在亨利·沃伦(Henry Warren)的《黑客的喜悦》一书中找到有关计数比特细节的整个章节。

关于algorithm - 在O(1)中计算汉明重量，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/15233121/