我在读《programming pearls by Jon Bentley》一书时遇到了这个问题。
给定一个非常长的字节序列(例如，数十亿或数万亿)，您将如何有效地计算一位的总数？(即序列中打开了多少位)
我见过的大多数解决方案都不会被认为是有效的。你认为如何有效地解决这个问题？
获取一个具有popc16指令的CPU(该指令对16字节大存储区中的1位进行计数；popc表示总体计数)，并在展开的循环中调用该指令。
如果速度仍然太慢，可以将数据拆分为多个块，并在独立的机器上进行处理。拆分或合并数据时，请注意不要造成瓶颈。
如果绑定到C，请检查编译器是否提供了__builtin_popc函数。
如果这是不允许的，请阅读《黑客的喜悦》一书。
高效。
当存在已知的没有相关缺点的更好的解决方案时，或者当该解决方案与理论最优解决方案相比时不浪费资源时，该解决方案是低效的。例如，我们有几种有效的噪声信道编码方法，它们接近已知的理论极限。
不幸的是，当我们有几个指标可以选择时——使用的资源、消耗的功率、使用的带宽、产生的延迟——效率就成了一个模糊的概念。计算机算法就是这样高效，在什么意义上？
2016年使用的典型台式机和服务器处理器使用多级缓存架构，其算术逻辑单元远远超过其主内存带宽。因此，即使在硬件中提供popcount功能的体系结构上，使用一种已知的比特篡改技巧来计算每个数据字中的数字也可能没有速度差异——至少当有太多数据无法放入缓存时是这样。
通常，算法的缓存占用空间会被忽略。如果它很大，该算法将有效地使用微基准中的缓存，给出非常好的效率数据，但由于它污染了缓存，它可能会减慢现实生活中不相关的操作，导致整体性能"莫名其妙"的下降。我们甚至没有任何"缓存效率"指标，因为它不仅在硬件模型之间不同，而且在工作负载和围绕算法实现本身执行的任务之间也不同。
更常见的情况是，程序员专注于使用最少的CPU时间对代码进行微基准测试，但忘记了绝大多数用户根本不在乎这一点，他们只希望任务占用最少的墙上时钟时间。换句话说，使用的CPU时间对用户来说很少像引起的延迟那样重要。传统的sort程序练习就是一个很好的例子。大多数人将文件读入一个行数组，然后煞费苦心地优化排序函数，以尽可能快地根据需要对其进行排序。他们忘记了阅读是一项缓慢的工作。将每一行读取到排序数据结构中，例如二进制搜索树(可能是平衡的)或其他树结构，可以完成大部分实际排序，而程序只需等待I/O完成。最终的结果是，虽然树方法很容易使用更多的CPU时间，但只要I/O花费任何可观的时间(即，数据尚未缓存)，它就会更快。
在这个特定的问题中，没有延迟问题，只有缓存行为，这可能会区分解决方案。我将实现大致分为两类：
-
直接位计数
分析每个字节或字(无符号整数单元)，并保持集合位的运行和的方法。
字节或字中设置的位数可以使用
popcount()类型的函数或通过表查找进行计数。 -
数值柱状图；结果是直方图和每个bin索引中设置的位数之间的点积
例如，一种方法可以使用
1U << CHAR_BIT条目(C中类型为size_t)来计数在存储器区域中看到的不同unsigned char值的数量。之后，所看到的设置比特的总数是每个条目的总和乘以在相应值中设置的比特的数量(OEIS A000120，但通常只是使用popcount()函数计数)。
在某些情况下，计算设置位的数量所花费的时间可能很重要(要么是出于安全原因，如果这恰好是某个安全机制的一部分，要么是因为这是在硬件中断上下文中完成的，并且如果抖动总是大致相同的持续时间，则引起的抖动最容易管理)，直方图方法可能更可取——效率更高——尽管它在第一次遇到时看起来效率很低。
直接位方法可能在许多方面效率低下。例如，您的C编译器可能根本不公开硬件popcount()函数，或者它可能会愚蠢地模仿它。在微控制器上，表查找可能位于闪存中，其访问速度可能比SRAM慢。也可能没有足够的SRAM可用于直方图方法。
虽然通过简单地展示一种缺点较少的方法很容易展示出一些效率低下的东西，但如果不知道比较的确切指标，也不知道如何衡量完全不同方法之间的效率，就不可能宣称某些东西是最高效的。
幸运的是，OP问如何。。。有效。这很好。不幸的是，因为有很多高效的方法，所以有很多方法可以完成指定的任务，硬件和上下文的差异决定了哪种方法"最好"或比另一种更高效。
询问"哪种方法的缺点最小…">会更好。根据我的意见和经验，这将是一种直接的方法，它使用unsigned long单元来处理大量数据，使用unsigned char来处理前导未对齐和尾随字节，以及使用popcountl()函数来计数无符号长中设置的位数。如果编译器是GCC，该函数将使用__builtin_popcountl()，否则将使用基于其中一个比特旋转技巧的static inline函数。
根据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的数量。