在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是什么意思）？

- NSF

---

旁注：实际上它不是 O(1)，而是与位数成对数关系的 O(log(n))，而一个简单的循环是 O(n)。对于固定的整数大小，这个算法和一个简单的循环都是 O(1)。 - Mysticial

@Mysticial 是的，如果我们考虑一个32位整数，它们都是O（1）。但是这个应该比迭代计数更快，对吧？ - NSF

@NSF - 是的，它可能比迭代计数更快（虽然它有一个乘法运算，所以...），但这不是大O分析的重点。大O指的是运行时间随输入大小增长的速度。在大O中，线性计数为O(n)，而此算法为O(log(n))，在渐近意义下确实更好，但有时渐近更快的算法可能需要特定的n值才能表现更好。 - Dylan McNamee

我不确定这是否算作O(log(n))。从时间上来看，它确实是O(log(n))的，但它通过需要O(n)并行化来实现这一点，以一种方式累加到O(n)总计算能力（如果您在整个[大]文件上运行此算法，这一点将变得明显）。 - Brilliand

Answer 1

这是一种用于计算比特的分治策略，称为“population”函数。学术上对此策略的处理可在Reingold和Nievergelt（1977）中找到。

其思想是首先两两相加比特，然后四四相加，然后八八相加，以此类推。例如，如果您有比特1011，那么第一对10变成01，因为有一个比特，第二对变成10，因为10 = 2在二进制中，而11中有两个比特。这里的基本事实是：

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

The exact algorithm you have is a variant of what is known as the "HAKMEM" algorithm (see Beeler, Gosper and Schroppel, 1972). This algorithm counts 1's in 4-bit fields in parallel, then these sums are converted into 8-bit sums. The last step is an operation to add these 4 bytes by multiplying by 0x01010101. The 0x0F0F0F0F mask gets the 4-wise bytes sums by masking out non-sum information. For example, lets say the 8-wise field is 10110110, then there are 5 bits which is equal to 0101, thus we will have 10110101. Only the last four bits are significant, so we mask out the first four, ie:

10110101 & 0x0F = 00000101

你可以在亨利·沃伦的书《Hacker's Delight》中找到一整章关于计算比特位的细节。

- Tyler Durden