现代计算机的硬件设计建立于数字电路的基础之上，而数字电路采用以2为基数的二进制记数系统。由此，二进制及其数字位（称为比特）的运算构成计算机系统软件的基石。一个常见的程序员面试题，就是比特位计数，即计算给定整数的二进制表示中比特1的个数。
People who deal with bits should expect to get bitten.
— Jon Bentley（乔恩·本特利，美国计算机科学家，计算机科学经典名著《编程珠玑》的作者，也以基于启发式的分区算法k-d树而知名）
这并不是一道很难的题目，但是要给出令人印象深刻的答案，却需要对二进制及比特位运算的深入理解，以及坚实的系统编程技巧和经验。实际上，比特位计数功能有悠久的历史。在早期的晶体管计算机时代，就有专门执行该功能的指令。如果主机的CPU指令集不支持此类指令，就必须使用软件代码实现。由于这一功能也常常被称为“种群统计”（population count），本文中所有解法的函数命名都以popcount_为前缀。下面我们来解析和评介这一面试题的各种解法和C语言实现。
如果熟悉基本的比特位运算操作（取反、与、或、异或、左/右移位），就可以很快找到一个解题的思路：生成一个单比特数0b1，将它与要计数的整数做位与运算，结果为1说明整数最右边的比特为1，否则为0；将此单比特数左移一位得到0b10，再与原整数做位与运算，用结果判定从右边起的第二位比特是否为1；重复此左移和位与运算，就能够从右到左扫描到所有的比特1并计数。如下的代码实现了这一简单直接的解法：
1 | int popcount_common1 (uint32_t n) |
与之类似的解法，是固定单比特数0b1，而将输入整数逐次右移，这样所有的高位比特都可以移到最右边来检测。利用比特位右移运算时最左边补上符号位的特点，此解法可能不需要循环32次而提前结束，循环的次数等于最高位比特1与最右边比特的比特距离。以下的代码展示了这一解法：
1 | int popcount_common2 (uint32_t n) |
考虑一个单字节8比特的整数n, 其数值为0x94，以二进制表示为0b10010100。如下图所示，如果将n减去1，得到0b10010011，即0x93。仔细观察二者的区别，减1后原整数最右边的比特1及后面的比特0全部取反，而其之前的比特位均保持不变。这时，如果将二者做位与运算，结果是0b10010000（0x90），最右的比特1被清除了！重复减1后位与操作，会得到0b10000000 (0x80)，原整数从右边数第二个比特1被清除了。第三次同样的操作完成，得到0，即原来的全部三个比特1都被清零。
总结这一规律：将一个整数减去1，再同原整数做位与运算，得到的结果等于原整数最右边的比特1清零；在最终结果变成0之前，能重复进行这样的操作的次数，就是原整数中比特1的数目。基于这一规律，我们可以写出新的计数函数代码：
1 | int popcount_fast1 (uint32_t n) |
无独有偶，还有一种与之对称的解法，适用于比特1个数较多（即比特0较少）的情况。参考下图，整数数值为0xBD，二进制表示为0b10111101。如果将n加上1，得到0b10111110，即0xBE。对比二者，加1后原整数最右边的比特0及后面的比特1全部取反，而其之前的比特位均保持不变。这时，如果将二者做位或运算，结果是0b10111111（0xBF），最右的比特0被置位了！重复加1后位与操作，会得到0b11111111 (0xFF)，原整数从右边数第二个比特0被置位了。这时原来的全部两个比特0都被置位，解法终止，原整数中比特1的个数等于总比特数减去重复操作的次数。
总结新的规律：将一个整数加上1，再同原整数做位或运算，得到的结果等于原整数最右边的比特0置位；在最终结果变成全比特1（等同于有符号数-1）之前，能重复进行这样的操作的次数，就是原整数中比特0的数目，而原整数中比特1的个数等于总比特数减去比特0的数目。这一规律对应的计数函数代码如下：
1 | int popcount_fast2 (uint32_t n) |
在具体的应用场景中，如果要处理的数据量很大，达到GB甚至TB量级，并且已知绝大部分数值的比特1个数都是较少（或较多）的状况，还可以将循环语句展开，进一步加快运行速度。
以上两种快速解法的循环展开实现如下。代码先定义宏f(x)和g(x)用来检测结果并即时返回计数值，然后在函数实现中拿掉while循环，取而代之的是分别反复调用f(x)和g(x)。在任何一步满足if条件为真，就会马上返回。这实际上是一种以空间换时间的方案。虽然函数代码及编译后的指令数目会增加不少，但是在运行过程中，因为每次检测都减少了一个算术运算指令（用于更新计数变量），所以运行会更快。
1 |
|
如前所述，快速解法是比特1个数较少或较多的情况下的优选。在平均计数值为总比特数的一半时，仍然需要相当多的指令完成任务。对于前例的popcount_fast1和popcount_fast2函数，平均需要循环16次，每次执行三次算术运算和一次比较/分支操作，最少64条操作指令。还有没有更好的、需要更少指令的通用解法呢？
当然有！早在40多年以前，三位美国计算机科学家Reingold、Nievergelt和Deo所著的《组合算法：理论和实践》1一书中，就详细讨论了一种应用“分而治之”（Divide and Conquer）策略的解法。这种解法是如此精妙，乃至应该将其升格以算法称呼才合适。下图演示了以16位的双字节数0xBFA6为例的计算过程，算法首先把相邻的两个比特位组合为一个位段，将这两个比特位的值相加，结果置于这个宽度为2的比特位段中。下一步把相邻的两个双比特位段的值相加，结果置于宽度为4的比特位段中。以此类推，四步之后就得到数值11（0x000B），正好就是原整数中比特1的总数。
这一看似帽子戏法的算法，是“分而治之”策略的典型应用。一个16位整数的比特1计数问题，被转化为两个8位整数的计数问题，分别解决后再将结果相加合并。递归运用此策略，直至分解到单个比特计数的问题。然后反复运用并行位运算求解再合并，即可求出最终的计数值。很明显，给定N比特位整数，此算法的时间复杂性是\(O(\log N)\)。
1 |
|
值得说明的一点是，此函数实现中的圆括号都是必要的。这是因为在C语言运算符的优先级次序表里，加减（+、-）要高于移位(<<、>>)，而后者又高于比特位运算（&、^、|）2。在n >> 1两边加圆括号则有助于增强代码的可读性。
另外，函数的第一行（上面代码段行号4）按照算法描述本来应该写成(n & 0xAAAAAAAA) >> 1，之所以这么写是为了避免在寄存器中生成两个大的常数。如果使用0xAAAAAAAA，在不支持单个“and not”指令的计算机里，就必须多耗费一条指令先将0x55555555取反，再与n做位与运算。后面四行的写法也出于同样的考虑。统计下来，这种“分而治之”算法的实现运算量恒定，总共只有20次算术运算操作，运行速度达到了快速解法平均速度的三倍多！
1 |
|
真的有！有经验的系统程序员都知道，许多现代计算机处理器的设计都支持单条乘法指令。由此把一个数乘以0x01010101，等于将其每个长度为8的比特位段相加求和，结果置于最高的字节中，所以只要右移24位就可以得到我们要的计数值。根据这一点，我们可以得到“分而治之”算法的最优实现版本：
1 |
|
使用GCC编译器特定选项，可以生成混合C代码及对照汇编语言的列表（list）文件，用来验证popcount_dnq3实现的优越性。在运行于Intel处理器的Ubuntu Linux x86-64虚拟机上，执行以下命令：
1 | 106:popcount.c **** int popcount_dnq2 (uint32_t n) |
可以看到，popcount_dnq2实现里右移8/16位相加各自有三条指令（行号973、974、976和978、979、981），最后的位与0x3F有两条指令（行号983、984），一共8条指令；而在popcount_dnq3实现中只有两条：一条加载指令movl和一条乘法指令imull。popcount_dnq3完胜！
还有一种以空间换时间的“分而治之”方案，虽然看上去比较无趣，但是其执行效率却可与上面的其他算法比肩。这种解决方案预设一个256项的数组，填入0～255之间每个数的比特位计数值，之后对于输入的整数依次取出单个字节查表，然后将结果相加。以下是无比较/分支指令的代码实现：
1 | const char popcount_tab[256] = |
透彻掌握本节的内容，一定可以让面试官对你刮目相看，因为你写出的代码，实现的就是广为认可的高效算法。不信去下载GCC最新的11.1.0版本，看看库文件libgcc/libgcc2.c里的比特位计数函数（复制如下），与前面的代码实质上是一样的：
1 | int |
比特位计数当然不仅仅是用来考验面试者的，它广泛应用于信息学、纠错编码和密码学等多个领域。实际上，“种群统计”就是二进制符号数据的汉明重量4。而两个数据比特串的汉明距离，就定义为二者对应位置上不同比特的个数，即二者相异或后的汉明重量。基于汉明距离的分析是密码分析学的一个关键技术，是历史上破解许多密码的关键。从比特位计数的算法，也衍生出一些快速计算汉明距离的算法，感兴趣者可以留言讨论。
事实上，比特位计数是如此重要，乃至GCC和Clang编译器都提供了内建库函数__builtin_popcount。Intel、AMD和ARM处理器也都为之设定了专门的指令。如下在运行于Intel处理器的Ubuntu Linux x86-64虚拟机上，指定GCC选项-march=native后__builtin_popcount函数编译成单一指令popcntl：
1 | 159:popcount.c **** count = __builtin_popcount(num); |
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。