6

位计数可以通过多种方式完成，例如。具有设置位迭代器、未设置位迭代器、具有查找表或并行计数的预计算位。正如我通过搜索网络发现的那样，当未设置位较少时，未设置位迭代器速度很快，而设置位迭代器则相反。但是什么时候应该使用并行计数，尤其是 MIT HAKMEM（见下文）？它看起来相当快，虽然可能比查找表慢。就速度而言，它总是比设置/取消设置位更好吗？除了速度和内存之外，还有其他一些关于选择哪一个的问题吗？

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

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

4 回答 4

5

为什么选择一种位计数方法而不是另一种？好吧，这实际上取决于您的机器和您要解决的问题。请注意，我在下面给出的所有指令计数都是针对基本 RISC 处理器的，可能无法很好地转换为像 x86 这样更复杂的野兽。

您引用的 HAKMEM 算法将在 13 条指令中执行，但由于模运算符，它不太可能非常快。通过观察它，它看起来确实具有一些非常好的指令级并行性，如果您的处理器能够利用它，这应该会有所帮助。

Bo Persson 提出的算法非常快（2 + 5*pop(x)指令），但前提是该词人口稀少。它也可以被修改以处理密集的单词。它还包含分支并且没有任何重要的指令级并行性。

编辑：表查找方法也可以非常快，但确实会进行内存访问。如果整个表都在 L1 缓存中，那么它可能是最快的算法之一。如果表不在缓存中，那么它几乎肯定是最慢的表之一。

下面的算法是 HAKMEM 算法之一的变体，在Hacker's Delight一书中有介绍（如果你喜欢这类东西，我强烈推荐这本书）。它以 19 条指令执行，并且是无分支的。它也不使用除法，但确实有乘法。通过尽可能多地重复使用相同的掩码来使用寄存器的方式也非常经济。我可以看到这里仍然没有显着的指令级并行性。

int pop(unsigned x) {
  unsigned n;

  n = (x >> 1) & 0x77777777;
  x = x - n;
  n = (n >> 1) & 0x77777777;
  x = x - n;
  n = (n >> 1) & 0x77777777;
  x = x - n;
  x = (x + (x >> 4)) & 0x0F0F0F0F;
  x = x * 0x01010101;
  return x >> 24;
}

Hacker's Delight 这本书还介绍了一些更专业的算法，用于 9-8-7 位宽的字段或使用浮点运算符。请注意，我上面介绍的大部分分析也部分取自那本书。

事实是，有一大堆方法，而确定哪种方法在您的特定情况下效果最好的唯一方法是测量和比较。我确实意识到这是一个非常固定的答案，但另一种方法是彻底了解您的处理器和编译器。

于 2012-01-10T06:12:21.527 回答
4

这非常简单，但如果只设置几个位，速度会非常快：

int popCount (U64 x) {
   int count = 0;
   while (x) {
       count++;
       x &= x - 1; // reset LS1B
   }
   return count;
}

来自国际象棋编程维基：Brian Kernighan 的方式

于 2012-01-10T00:09:22.117 回答
1

如果您有一个支持 SSE4 的 x86-CPU，那么您已经有了一条指令来完成所有工作：POPCNT。请参阅英特尔® SSE4 编程参考。(PDF, 698KB)

另一句话：像 HAKMEM 169 这样的并行算法不包含条件分支。这是一个巨大的优势。现代处理器预测条件分支的方向，但在随机分支模式方面存在问题。错误预测的成本非常高（成本可能超过 100 条指令）。如果性能很重要，最好避免使用可变循环计数和/或条件语句的循环。了解更多信息：

我也赞同 Book Hackers Delight的推荐。

于 2012-01-11T17:07:56.280 回答
0

像下面这样的东西怎么样：

  1. 从每个原始单词 r 中，计算一个配对单词为 `w = r - (r & 0x55555555)`。每对位将保存该对中设置位的数量 (0-2)。
  2. 接下来，从每个 pair-munged 单词中，计算一个 quad-munged word `q = (w & 0x33333333) + ((w >> 2) & 0x33333333)`。每个四重组设置位将保存该四重组中设置位的数量（0-4）。
  3. 以两个一组的形式将四重词组合在一起，并从每个和 `s` 计算八位字节的和`o = (s & 0x0F0F0F0F) + ((s >> 4) & 0x0F0F0F0F)`。每个八位字节将保存两个输入字 (0-16) 中相应八位字节中设置位的总数。
  4. 将八位字节的总和以八个一组相加，并从每个总和`s`计算一个半字的总和`h = (s & 0x00FF00FF) + ((s >> 8) & 0x00FF00FF)`。每个半字将包含所有 16 个输入字 (0-256) 的相应半字中的设置位总数。
  5. 以 128 个为一组将半字计算的总和相加，并从每个总和 `s` 计算总和 `t = (s & 0x0000FFFF) + ((s >> 16) & 0xFFFF)`。这将保存 1024 个输入字 (0-32768) 中的设置位数

请注意，对每个单词执行两个步骤，对每个其他单词执行一个步骤，对每 16 个单词执行一个步骤，对每 1024 个执行一个步骤。如果单词是 64 位而不是 32 位，则最终总和需要一个额外的步骤，但是单词拼凑的总和可以以 65,536 个为一组添加（代表 67,108,864 个输入单词）。

于 2012-01-11T00:45:26.223 回答