c - 如何在 O(1) 时间内找到二进制数中 1 的个数？

Question

我知道之前有人问过这个问题，但我正在查看列出的这个特定解决方案 here :

int BitCount(unsigned int u)
{
     unsigned int uCount;

     uCount = u - ((u >> 1) & 033333333333) - ((u >> 2) & 011111111111);
     return ((uCount + (uCount >> 3)) & 030707070707) % 63;
}

它是如何工作的？

这里有什么注意事项吗？

理论上是否可以在常数时间内找到答案？我的意思是，我们实际上不是必须遍历要计数的位吗？

Answer 1

计数位

无符号 32 位整数 u可以这样写:

u = a<sub>31</sub> * 2<sup>31</sup> + a<sub>30</sub> * 2<sup>30</sup> + ... + a<sub>0</sub> * 2<sup>0</sup>

我们想要 a<sub>31</sub> + a<sub>30</sub> + ... + a<sub>0</sub> 的值.

让我们比较一下 u >> k 的值:

u >> 0  = a31 * 231 + a30 * 230 + ... + a1 * 21 + a0 * 20u >> 1  = a31 * 230 + a30 * 229 + ... + a1 * 20u >> 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

让我们看看为什么会这样:

  u >> 0 - u >> 1 - u >> 2 - ... - u >> 31
= u >> 0 - (u >> 1 + u >> 2 + ... + u >> 31)
= u - q

q 的值是多少？ ？让我们一点一点地计算它，查看 u >> k 的值多于。对于 a<sub>31</sub> ，它是:

  a31 * 230 + a31 * 229 + ...= a31 * (230 + 229 + ...)= a31 * (231 - 1)

Or for a<sub>30</sub>:

  a30 * 229 + a30 * 228 + ...= a30 * (229 + 228 + ...)= a30 * (230 - 1)

We find: q = a<sub>31</sub> * (2<sup>31</sup> - 1) + a<sub>30</sub> * (2<sup>30</sup> - 1) + ...

And thus

u - q = a31 * 231 - a31 * (231 - 1) + ...      = a31 + a30 + ... + a0

Counting bits in 3-bit blocks

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 中相应八位组中设置的位数.

uCount      =   αβγδεζηθικλ (each greek letter is an octet)
uCount >> 3 =    αβγδεζηθικ

所以 uCount + (uCount >> 3)是(λ+κ) * 2<sup>0</sup> + (κ+ι) * 2<sup>3</sup> + (ι+θ) * 2<sup>6</sup> + ...

通过与 0o30707070707 进行与运算，我们屏蔽掉每隔一个八位位组，这样我们只对每对计数一次:

r = (λ+κ) *  20 + (ι+θ) *  26 + (η+ζ) *  212 + ...  = (λ+κ) * 640 + (ι+θ) * 641 + (η+ζ) * 642  + ...

这是一个 base-64 数字，我们想将 base-64 数字相加得到 α+β+γ+δ+ε+ζ+η+θ+ι+κ+λ ，我们的最终结果。为此，我们计算其 base-64 digital root : 知道结果永远不会大于 32，我们只需将数字除以 63。