O型计算的汉明权(1) [英] Calculating Hamming Weight in O(1)
问题描述
在二重presentation,汉明权重为1的数量。我遇到了网络,发现了一个O(1)的回答是:
In binary representation, hamming weight is the number of 1's. I came across web and found an O(1) answer to it:
v = v - ((v>>1) & 0x55555555);
v = (v & 0x33333333) + ((v>>2) & 0x33333333);
int count = ((v + (v>>4) & 0xF0F0F0F) * 0x1010101) >> 24;
不过,我不太了解该算法并不能找到它的描述在任何地方。是否有人可以解释这一点尤其是最后一行(到底做什么* 0x1010101然后>> 24的意思)?谢谢你。
However I don't quite understand the algorithm and cannot find a description of it anywhere. Can someone please explain it a little bit especially the last line (what the heck does *0x1010101 and then >> 24 mean)? Thanks.
推荐答案
这是一个分而治之的策略,用于计数位的一部分,所谓的人口的功能。学术处理这个策略可以在莱因戈尔德和Nievergelt,1977年被发现。
This is part of a divide-and-conquer strategy for counting bits, called a "population" function. The scholarly treatment of this strategy can be found in Reingold and Nievergelt, 1977.
我们的想法是第一总和位配对,然后4明智的,那么8明智等等。例如,如果你有位 1011
,然后第一对 10
变成 01
,因为有一个位和第二变 10 = 2
在$ C $ 10二进制和有在两位 11
。这里的基本事实是:
The idea is to first sum the bits pairwise, then 4-wise, then 8-wise and so on. For example, if you have the bits 1011
, then the first pair 10
becomes 01
because there is one bit and the second becomes 10
because 10 = 2
in binary and there are two bits in 11
. The essential fact here is that:
population(x) = x - (x/2) - (x/4) - (x/8) - (x/16) - ... etc.
确切的算法,你是所谓的HAKMEM算法的变体(见比勒,高斯帕和Schroppel,1972年)。该算法计数 1
的在并行4位字段,那么这些款项被转换为8位的总和。最后一步是一个操作由 0x01010101
相乘来添加这些4个字节。该 0x0F0F0F0F
面膜通过屏蔽掉非金额信息获取4明智的字节总和。例如,假设8明智的字段是 10110110
,然后有5位等于 0101
,因此,我们将有 10110101
。只有最后4位显著,所以我们屏蔽掉第4位,即:
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
您可以找到的书黑客的喜悦,由亨利·沃伦计数位的细枝末节整整一章。
You can find an entire chapter on the minutiae of counting bits in the book "Hacker's Delight" by Henry Warren.
这篇关于O型计算的汉明权(1)的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!