何时使用并行计数-当内存是一个问题时，MIT HAKMEM用于位计数

Question

位计数可以通过几种方式完成，例如:具有设置位迭代器，未设置位迭代器，带查找表或并行计数的预计算位。根据我在网上搜索的结果，unset bit iterator在unset bits较少的情况下比较快，而set bit iterator则相反。但是什么时候应该使用并行计数，特别是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)指令)，但只有在单词稀疏填充的情况下。它也可以被修改来处理密集的单词。它还包含分支，并且没有任何重要的指令级并行性。

EDIT:表查找方法也可以非常快，但是需要内存访问。如果整个表都在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位宽域或使用浮点运算符。请注意，我上面展示的大部分分析也部分摘自那本书。

事实是，有很多方法，唯一能确定哪种方法最适合你的特定情况的方法就是衡量和比较。我确实意识到这是一个相当老套的答案，但另一种选择是了解你的处理器和编译器。

Answer 2

这非常简单，但如果只设置几个位，则速度惊人:

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

From Chess programming wiki: Brian Kernighan的方式

Answer 3

如果你有一个支持SSE4的x86 cpu，你已经有一个指令来完成所有的工作:POPCNT。参见Intel®SSE4编程参考。(PDF, 698 kb)

另一个评论:像HAKMEM 169这样的并行算法不包含条件分支。这是一个巨大的优势。现代处理器可以预测条件分支的方向，但在处理随机分支模式时遇到麻烦。错误预测的代价是非常高昂的(代价可能超过相当于100条指令的代价)。如果性能很重要，最好避免使用可变循环计数和/或条件语句的循环。查看更多信息:

• Intel®64和IA-32架构优化参考手册(PDF, 4.5MB)
• AMD系列15h处理器软件优化指南(PDF, 1.9MB)

我也支持《黑客之乐》这本书的推荐。

Answer 4

不如这样写:

1. 从每个原始单词r中，计算一个配对后的单词' w = r- (r & 0x55555555) '。每一对比特将保存该对中设置的比特数(0-2)。
2. 接下来，从每个成对修改的单词中，计算一个四元修改的单词' q = (w & 0x33333333) + ((w>> 2) & 0x33333333) '。每个集合位的四重奏将保存该四重奏中的集合位的数量(0-4)。
3. 将四元化的单词以两组为一组求和，并从每个和' s ' '计算一个八位化的和' o = (s & 0x0f0f00f) + ((s>> 4) & 0x0f0f0f) ' '。每个八位元组将保存两个输入字(0-16)中对应八位元组中设置位的总数。
4. 将八位元修改后的和以8为一组进行求和，并从每个和'计算一个半字修改后的和' 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个输入单词)进行相加。