c++ - 何时使用并行计数 - 当内存有问题时使用 MIT HAKMEM 进行位计数？

Question

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

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

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

Answer 1

为什么选择一种位计数方法而不是另一种？好吧，这真的取决于您的机器和您要解决的问题。请注意，我在下面给出的所有指令数都是针对基本 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 位宽字段或使用浮点运算符的更专业的算法。请注意，我上面介绍的大部分分析也部分取自那本书。

事实上，有很多方法，要确定哪种方法最适合您的特定情况，唯一的方法就是测量和比较。我确实意识到这是一个很好的固定答案，但另一种选择是彻底了解您的处理器和编译器。