计算O(1)中的汉明重量

Question

在二进制表示中,汉明重量是1的数.我遇到了网络并找到了一个O(1)答案:

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

但是我不太了解算法,无法在任何地方找到它的描述.有人可以解释一下,尤其是最后一行(什么是*0x1010101然后>> 24意味着什么)？

Answer 1

这是计算比特的分而治之策略的一部分,称为"人口"功能.这种策略的学术处理可以在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位字段中的s,然后将这些和转换为8位和.最后一步是通过乘以来添加这4个字节的操作0x01010101.该0x0F0F0F0F掩模通过掩蔽掉非总和信息获取4-明智字节和.例如,假设8位字段是10110110,那么有5位相等0101,因此我们将拥有10110101.只有最后四位是重要的,所以我们屏蔽了前四位,即:

10110101 & 0x0F = 00000101

你可以在Henry Warren的"Hacker's Delight"一书中找到关于计数位的细节的完整章节.