如何有效地计算C中一长串字节中一位的总数？

Question

我在看书 programming pearls by Jon Bentley 时遇到了这个问题。

Given a very long sequence (say, billions or trillions) of bytes, how would you efficiently count the total number of one bits? (i.e how many bits were turned on in the sequence)

我见过的大多数解决方案都不被认为是有效的。您认为如何有效解决这个问题？

Answer 1

获取一个 CPU，它有一个 popc16 指令（它计算 16 字节大存储区域中的一位；popc 表示人口计数）并在展开的循环中调用它。

如果仍然太慢，将数据分成多个块并在独立的机器上处理它们。拆分或合并数据时注意不要造成瓶颈。

如果您绑定到 C，请检查您的编译器是否提供了 __builtin_popc 函数。

如果连这点都不允许，请阅读《Hacker’s Delight》一书。

Answer 2

根据 Roland 的回答，获取无符号（或一次 4 个字节）中 1 的个数的一种有效方法是以下按位黑客攻击（我相信这来自黑客的喜悦或位旋转黑客)

int getn1s (unsigned x)
{
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x = x + (x << 8);
    x = x + (x << 16);
    return x >> 24;
}

如果在展开的循环中内联和调用，对结果求和，应该提供一种相当有效的方法来计算尽可能多的字节中 1 的数量。

Answer 3

高效.

如果存在已知的没有相关缺点的更好解决方案，或者与理论上的最佳解决方案相比该解决方案不会浪费资源，则该解决方案效率低下。例如，我们有几种高效噪声信道编码方法，它们接近已知的理论 limit.

不幸的是，当我们有多个指标可供选择时——使用的资源、消耗的功率、使用的带宽、产生的延迟——，效率就变成了一个模糊的概念。计算机算法就是这种情况。高效，在什么意义上？

2016 年使用的典型台式机和服务器处理器使用多级缓存架构，并具有远远超过其主内存带宽的算术逻辑单元。因此，即使在硬件中提供 popcount 功能的体系结构上，使用一种已知的位摆弄技巧来计算每个数据字中的数字也可能没有速度差异——至少当有太多数据无法计算时适合缓存。

通常，算法的 缓存足迹 会被忽略。如果它很大，该算法将在微基准测试中有效地使用缓存，给出非常好的效率数据，但由于它污染了缓存，它可能会减慢实际生活中不相关的操作，从而导致整体性能下降 "inexplicable"。我们甚至没有任何 "cache efficiency" 指标，因为它不仅在硬件模型之间变化，而且在工作负载和围绕算法实现本身执行的任务之间变化。

更常见的是，程序员专注于使用最少量的 CPU 时间对他们的代码进行微基准测试，但忘记了绝大多数用户根本不关心这一点，他们只是更喜欢任务取而代之的是花费最少的挂钟时间。换句话说，CPU 使用的时间很少像 发生的延迟 对用户那么重要。一个很好的例子就是传统的 sort 程序练习。大多数将文件读入行数组，然后煞费苦心地优化排序函数以根据需要尽可能快地对它们进行排序。他们忘记了阅读是一项缓慢的工作。将每一行读入排序数据结构，例如二叉搜索树，可能是平衡的，或其他一些树结构，允许完成大部分实际排序，否则程序只需等待 I/O 完成。最终结果是，虽然树方法更容易使用更多 CPU 时间，但只要 I/O 花费任何可观的时间（即数据尚未缓存），它就会更快。

在这个特定问题中，没有延迟问题，只有缓存行为，这可能会导致解决方案有所不同。我将实现大致分为两个类别：

直接位计数

分析每个字节或字（无符号整数单元）并保留运行个设置位总和的方法。

可以使用 popcount() 类型函数或通过 table 查找来计算字节或字中设置的位数。
值直方图；结果是直方图和每个 bin 索引中设置的位数之间的点积

例如，一种方法可以使用 1U << CHAR_BIT 条目（在 C 中属于 size_t 类型）来计算内存区域中出现的不同 unsigned char 值的数量。之后，看到的设置位数的总数是每个条目的总和乘以相应值中设置的位数（OEIS A000120，但通常只是使用 popcount() 函数计算）。

在某些情况下，计算设置位数所花费的时间可能很重要（出于安全原因，如果这恰好是某些安全机制的一部分，或者因为这是在硬件中断上下文中完成的如果持续时间大致相同，则引起的抖动最容易管理），直方图方法可能更可取——更高效 —— 虽然一开始看起来效率很低相遇

直接钻头方法在很多方面效率不高。例如，您的 C 编译器可能根本不会公开硬件 popcount() 函数，或者它可能会以某种愚蠢的方式模拟它。在微控制器上，table 查找可能驻留在闪存中，闪存的访问速度可能比 SRAM 慢。也可能没有足够的 SRAM 可用于直方图方法。

虽然通过简单地展示缺点较少的方法很容易表明某些东西效率低下，但如果不知道确切的情况就不可能声称某些东西最有效比较的指标，完全不同的方法之间的效率究竟是如何衡量的。

幸运的是，OP 询问了如何...高效。那很好。不幸的是，因为有很多方法可以提高效率，所以有很多方法可以完成指定的任务，硬件和上下文的差异决定了哪种方法 "best" 或比另一种更有效。

问"which approach has the least downsides to ..."会更好。以我的观点和经验，这将是一种直接的方法，它使用 unsigned long 单位来处理大量数据，使用 unsigned char 来处理前导未对齐字节和尾随字节，并使用 popcountl() 函数来计算数量在无符号长整数中设置的位。如果 compiler is GCC，该函数将使用 __builtin_popcountl()，否则将使用基于其中一个位旋转技巧的 static inline 函数。

如何有效地计算C中一长串字节中一位的总数？

How to efficiently count the total number of one bits in a long sequence of bytes in C?

c

bits