如何找到的1的数目在在O（1）时间二进制数？ [英] How to find number of 1's in a binary number in O(1) time?
问题描述
我知道这已经问过，但我正在寻找在这个特别的解决方案上市这里：
I know this has been asked before, but I'm looking at this particular solution listed here:
int BitCount(unsigned int u)
{
unsigned int uCount;
uCount = u - ((u >> 1) & 033333333333) - ((u >> 2) & 011111111111);
return ((uCount + (uCount >> 3)) & 030707070707) % 63;
}
它是如何工作的？
How does it work?
是否有这里涉及到什么注意事项？
Are there any caveats involved here?
在理论上是有可能找到在固定时间的答案吗？我的意思是我们不实际的有无的遍历位来算？
Theoretically is it possible to find the answer in constant time? I mean don't we actually have to iterate through the bits to count?
推荐答案
这是32位无符号整数 U 可以这样写：
Counting bits
An unsigned 32-bit integer u can be written like this:
U =一 31 * 2 31 + A 30 * 2 30 + ... + A <子> 0 * 2 0
u = a31 * 231 + a30 * 230 + ... + a0 * 20
我们想要的 A 31 的值+ A 30 + ... + A <子> 0 。
We want the value of a31 + a30 + ... + a0.
让我们比较的数值 U＆GT;＆GT;氏/ code>：
Let's compare the values of u >> k:
u >> 0 = a31 * 231 + a30 * 230 + ... + a1 * 21 + a0 * 20
u >> 1 = a31 * 230 + a30 * 229 + ... + a1 * 20
u >> 2 = a31 * 229 + a30 * 228 + ...
...
u >> 29 = a31 * 22 + a29 * 21 + ...
u >> 30 = a31 * 21 + a30 * 20
u >> 31 = a31 * 20
我们将计算出位居民通过这个公式：
We will calculate the bit population by this formula:
u >> 0 - u >> 1 - u >> 2 - ... - u >> 31 = p
让我们来看看为什么这个作品：
Let's see why this works:
u >> 0 - u >> 1 - u >> 2 - ... - u >> 31
= u >> 0 - (u >> 1 + u >> 2 + ... + u >> 31)
= u - q
什么是①的价值？让我们来计算它的点点滴滴，在看值 U＆GT;＆GT;氏/ code>上方。对于 A 31 ，它是：
What's the value of q? Let's calculate it bit by bit, looking at the values for u >> k above. For a31, it's:
a31 * 230 + a31 * 229 + ...
= a31 * (230 + 229 + ...)
= a31 * (231 - 1)
或为 A 30 ：
Or for a30:
a30 * 229 + a30 * 228 + ...
= a30 * (229 + 228 + ...)
= a30 * (230 - 1)
我们发现： Q =一 31 *（2 31 - 1）+一个 30 *（2 30 - 1）+ ...
We find: q = a31 * (231 - 1) + a30 * (230 - 1) + ...
和由此
u - q = a31 * 231 - a31 * (231 - 1) + ...
= a31 + a30 + ... + a0
这个算法开始做同样的事情，但在3位块：
This algorithm starts by doing the same thing, but in blocks of 3 bits:
u >> 0 = AaBbbCccDddEeeFffGggHhhIiiJjjKkk (each letter is a bit)
u >> 1 & 033333333333 = A Bb Cc Dd Ee Ff Gg Hh Ii Jj Kk (blank = zero)
u >> 2 & 011111111111 = B C D E F G H I J K
考虑到这些差别，按上述算法，每一个字节 uCount 包含 U <设置相应字节位数/ code>。
Taking the difference of these, by the above algorithm, each octet in uCount contains the number of bits set in the corresponding octet in u.
uCount = αβγδεζηθικλ (each greek letter is an octet)
uCount >> 3 = αβγδεζηθικ
所以 uCount +（uCount＆GT;＆GT; 3）是（λ+κ）* 2 0 + （κ+ι）* 2 3 +（ι+θ）* 2 6 + ...
So uCount + (uCount >> 3) is (λ+κ) * 20 + (κ+ι) * 23 + (ι+θ) * 26 + ...
通过AND运算与 0o30707070707 ，我们走掩盖所有其他字节，让我们只算每对一次：
By ANDing with 0o30707070707, we mask away every other octet, so that we only count each pair once:
r = (λ+κ) * 20 + (ι+θ) * 26 + (η+ζ) * 212 + ...
= (λ+κ) * 640 + (ι+θ) * 641 + (η+ζ) * 642 + ...这是一个base-64号，我们要总结的基础-64出局α+β+γ+δ+ε+ζ+η+θ+ι+κ+ λ，我们的最终结果。要做到这一点，我们计算其基准64 数字根：在明知其结果可能比32绝不会更大，我们刚模数除以63。
This is a base-64 number, and we want to sum up the base-64 digits to get α+β+γ+δ+ε+ζ+η+θ+ι+κ+λ, our final result. To do this, we calculate its base-64 digital root: knowing that the result can never be bigger than 32, we just modulo the number by 63.
这篇关于如何找到的1的数目在在O（1）时间二进制数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
