logo标签列表

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

calgorithmbit-manipulation
4

我知道之前已经有人问过这个问题，但我正在查看这个特定的解决方案，它在这里列出：

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

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

它是如何工作的？

这里有什么注意事项吗？

从理论上讲，在常数时间内找到答案是可能的吗？我是说我们难道不需要遍历比特位来计数吗？

2
除非你处理多精度数字，否则通过比特迭代的时间是恒定的 --- 常数是整数位大小。 - Barmar
3
从技术上讲，一个 unsigned int 是 4 个字节，如果你总是遍历 int 中的所有 32 位，无论 N 的值如何，那么从技术上讲它是 O(1)。请记住，O(1) 意味着时间复杂度不会随着 N 的值而改变。 - Shashank
1
注意：这仅适用于32位输入（无符号整数）。因此，输入已知且长度恒定，因此一些花哨的位运算可以得出答案。如果长度不恒定，则迭代几乎是不可避免的。 - Benjamin Trent
请注意，如果N没有上限，则算法必须为O(log N)。 - Shashank
虽然这是一个有趣而且也许具有指导意义的解决方案，但是使用非2的幂进行取模通常比其他几种选择更慢，比如这个或者使用几个查表（通常是使用一个256项的表）。 - harold
显示剩余4条评论
4个回答
11

比特计数

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

u = a31 * 231 + a30 * 230 + ... + a0 * 20

我们想知道 a31 + a30 + ... + a0 的值。

让我们比较 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

我们将使用以下公式计算比特数：

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的值。对于a31，它为：

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

或者对于a30：

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

我们发现：q = a31 * (231 - 1) + a30 * (230 - 1) + ...

因此，

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

以3位块为单位计算位数

这个算法从做同样的事情开始，但是以3位块为单位：

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)就是(λ+κ) * 20 + (κ+ι) * 23 + (ι+θ) * 26 + ...

通过与0o30707070707的AND运算，我们掩盖了每个其他八进制数位，这样我们只计算每一对仅一次：

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

这是一个64进制数，我们想要将其各位数字相加，得到α+β+γ+δ+ε+ζ+η+θ+ι+κ+λ，我们的最终结果。为此，我们计算它的64进制数字根: 知道结果永远不会大于32，我们只需将数字模63。

5

迭代位是常数时间，因为类型中的位数是恒定的。

因此，检查目标值中每个位并进行移位的解决方案确实是O(1)（例如，其中常数为32）。

1
我没有给你的回答点踩，你的答案是正确的，但我认为他想说的是高效时间而不是O(1)复杂度。这个问题确实表述不清，但看起来他只是想了解如何在没有循环的情况下完成这个任务。 - Leeor
我认为O(1)时间是指排除循环遍历位数（即O(n)时间）的解决方案，包括底层的这种解决方案或例程，因此我认为它只使用二进制算术作为一个整体实体而不是每个位上的二进制算术。顺便说一句，我想问完全相同的问题，但是要找到（最高位）设置位的位置（即在O(1)中的二进制对数）。 - Nikos M.
5

最快的方法是使用popcnt指令。通常可以通过编译器内置函数来访问它。如果在某些平台上缺少此指令，则您的解决方案可能会很有用。

1

计算并行位集展示了如何完成此操作。该方法可用于8、16、32、64、128等位的字，尽管计算中使用的常量会改变。

当我们说这个操作是O(1)时，我们的意思是它可以在常数时间内完成，无论字的大小如何。用朴素的方式计算比特是O(n)，其中n为比特数。

实际上，只有处理器可以原生地处理字大小时，才能达到O(1)。

至于它是如何工作的，它使用了“魔法数字”。请参见这篇新闻组帖子以获得解释。

1
Downvoter，有什么想分享的吗？通常需要提供一个降低评分的理由。 - Jim Mischel
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接