程序员面试题精解(1)— 比特位计数

现代计算机的硬件设计建立于数字电路的基础之上,而数字电路采用以2为基数的二进制记数系统。由此,二进制及其数字位(称为比特)的运算构成计算机系统软件的基石。一个常见的程序员面试题,就是比特位计数,即计算给定整数的二进制表示中比特1的个数。

Low-level programming is good for the programmer's soul.
John Carmack(约翰·卡马克,美国电玩游戏程序员、id Software的创始人之一)

这并不是一道很难的题目,但是要给出令人印象深刻的答案,却需要对二进制及比特位运算的深入理解,以及坚实的系统编程技巧和经验。实际上,比特位计数功能有悠久的历史。在早期的晶体管计算机时代,就有专门执行该功能的指令。如果主机的CPU指令集不支持此类指令,就必须使用软件代码实现。由于这一功能也常常被称为“种群统计”(population count),本文中所有解法的函数命名都以popcount_为前缀。下面我们来解析和评介这一面试题的各种解法和C语言实现。

常规解法

常规的解法是每一个初级程序员都必须掌握的。以32位整数2418146236为例,

  • 十六进制表示:0x9021FBBC
  • 二进制表示:0b 10010000 00100001 11111011 10111100
  • 比特1的个数:16

如果熟悉基本的比特位运算操作(取反、与、或、异或、左/右移位),就可以很快找到一个解题的思路:生成一个单比特数0b1,将它与要计数的整数做位与运算,结果为1说明整数最右边的比特为1,否则为0;将此单比特数左移一位得到0b10,再与原整数做位与运算,用结果判定从右边起的第二位比特是否为1;重复此左移位与运算,就能够从右到左扫描到所有的比特1并计数。如下的代码实现了这一简单直接的解法:

1
2
3
4
5
6
7
8
9
10
11
int popcount_common1 (uint32_t n)
{
int c = 0;
int i = 0;
while (i < 32) {
if (n & (1 << i))
c++;
i++;
}
return c;
}

可以看到,这种解法的运算量只取决于输入整数类型的总比特数,而与整数本身的数值无关。如上的函数定义,因为输入为32位无符号数,所以代码中循环和移位次数也为32。

与之类似的解法,是固定单比特数0b1,而将输入整数逐次右移,这样所有的高位比特都可以移到最右边来检测。利用比特位右移运算时最左边补上符号位的特点,此解法可能不需要循环32次而提前结束,循环的次数等于最高位比特1与最右边比特的比特距离。以下的代码展示了这一解法:

1
2
3
4
5
6
7
8
9
int popcount_common2 (uint32_t n)
{
int c = 0;
while (n) {
c += n & 1;
n >>= 1;
}
return c;
}

对于上面的第二种常规解法的C函数实现,有三点要提醒注意:

  1. 解法利用了右移时最左边补上符号位0的特点,所以可以根据移位后数是否为0,来确定需不需要提前结束循环。这是优于第一种常规解法的地方。但是也由此限定了输入n必须为无符号数,否则当输入为负数时,右移时最左边的符号位会移到数据位,而且还会又补上符号位1。这样最终n会变为0xFFFFFFFF,程序落入死循环!解决此问题的办法是,如果函数定义的输入是int32_t,要先将之强制类型赋值到无符号数uint32_t,再执行相同的检测和计数步骤。基于此处理,本文余下内容所提到的整数皆为无符号数。
  2. 以上代码第5行不是应该写成if (n & 1) c++;吗?为什么变成c += n & 1;?其实两种写法结果一样,但实际中后者可能会优于前者。现代计算机处理器都是基于流水线(pipeline)的设计以提高指令执行速度,而if语句编译成的分支指令,会造成流水线冲突而拉低执行效率。当然,依赖于特定的计算机体系结构和编译器优化能力,这一区别也有可能太小乃至可以忽略不计。
  3. 以上代码第6行右移一位,等价于将整数除以2。那么请问可以把它写成n /= 2;吗?绝对不行!这是面试官设置的陷阱。只要学过计算机组成的基础知识,就应该知道除法的执行效率远低于移位运算,所以实际中要尽量避免使用除法。

快速解法

实现常规解法可以验证面试者是否拥有初级程序员的基本技能。然而,对于中高级程序员的职位,面试官会要求效率更高的解法。那么,存在更快的解法吗?答案是肯定的。

考虑一个单字节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
2
3
4
5
6
7
8
9
int popcount_fast1 (uint32_t n)
{
int c = 0;
while (n) {
c++;
n &= (n-1);
}
return c;
}

毫无疑问,由于循环的次数取决于比特1的数目,这种解法当然比常规解法要快。在比特1个数不多的场合,这是优选的快速解法。

无独有偶,还有一种与之对称的解法,适用于比特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
2
3
4
5
6
7
8
9
int popcount_fast2 (uint32_t n)
{
int c = 32;
while (n != -1) {
c--;
n |= (n+1);
}
return c;
}

同理,由于循环的次数取决于比特0的数目,在比特1个数较多的场合,这是优选的快速解法。

在具体的应用场景中,如果要处理的数据量很大,达到GB甚至TB量级,并且已知绝大部分数值的比特1个数都是较少(或较多)的状况,还可以将循环语句展开,进一步加快运行速度。

以上两种快速解法的循环展开实现如下。代码先定义宏f(x)g(x)用来检测结果并即时返回计数值,然后在函数实现中拿掉while循环,取而代之的是分别反复调用f(x)g(x)。在任何一步满足if条件为真,就会马上返回。这实际上是一种以空间换时间的方案。虽然函数代码及编译后的指令数目会增加不少,但是在运行过程中,因为每次检测都减少了一个算术运算指令(用于更新计数变量),所以运行会更快。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* If most bits are 0, use the following unrolled solution.*/
#define f(x) if ((n &= (n-1)) == 0) return x;
int popcount_fast1_unrolled (uint32_t n)
{
if (n == 0) return 0;
f( 1) f( 2) f( 3) f( 4) f( 5) f( 6) f( 7) f( 8)
f( 9) f(10) f(11) f(12) f(13) f(14) f(15) f(16)
f(17) f(18) f(19) f(20) f(21) f(22) f(23) f(24)
f(25) f(26) f(27) f(24) f(29) f(30) f(31)
return 32;
}

/* If most bits are 1, use the following unrolled solution.*/
#define g(x) if ((n |= (n+1)) == -1) return 32-x;
int popcount_fast2_unrolled (uint32_t n)
{
if (n == -1) return 32;
g( 1) g( 2) g( 3) g( 4) g( 5) g( 6) g( 7) g( 8)
g( 9) g(10) g(11) g(12) g(13) g(14) g(15) g(16)
g(17) g(18) g(19) g(20) g(21) g(22) g(23) g(24)
g(25) g(26) g(27) g(24) g(29) g(30) g(31)
return 0;
}

分而治之

如前所述,快速解法是比特1个数较少或较多的情况下的优选。在平均计数值为总比特数的一半时,仍然需要相当多的指令完成任务。对于前例的popcount_fast1popcount_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)\)

对于32位的整数,上图中的算法用C语言写出来就是:

1
2
3
4
5
6
7
8
9
10
/* Divide-and-Conquer - original (20 arithmetic operations) */
int popcount_dnq1 (uint32_t n)
{
n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
n = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F);
n = (n & 0x00FF00FF) + ((n >> 8) & 0x00FF00FF);
n = (n & 0x0000FFFF) + ((n >> 16) & 0x0000FFFF);
return n;
}

值得说明的一点是,此函数实现中的圆括号都是必要的。这是因为在C语言运算符的优先级次序表里,加减(+-)要高于移位(<<>>),而后者又高于比特位运算(&^|2。在n >> 1两边加圆括号则有助于增强代码的可读性。

另外,函数的第一行(上面代码段行号4)按照算法描述本来应该写成(n & 0xAAAAAAAA) >> 1,之所以这么写是为了避免在寄存器中生成两个大的常数。如果使用0xAAAAAAAA,在不支持单个“and not”指令的计算机里,就必须多耗费一条指令先将0x55555555取反,再与n做位与运算。后面四行的写法也出于同样的考虑。统计下来,这种“分而治之”算法的实现运算量恒定,总共只有20次算术运算操作,运行速度达到了快速解法平均速度的三倍多!

到这里,如果面试者对以上全部的解法都有清晰的思路并写下无错的代码,应该可以得到面试官的首肯。再往下的知识点,就是属于能给面试官带来惊喜的技能了。

锦上添花

问还可以更快吗?

是的,上述“分而治之”算法的代码实现还能进一步优化:

  1. 仔细审查函数popcount_dnq1返回语句之前的三行(代码段行号6、7、8),你会发现一些位与操作是多余的。一则,在这些步骤中比特位段求和的结果不可能向左边的比特位段进位;二则,在最后一步,高位的比特值是可忽略的,计数结果只在最右边的m位比特中,这里\(m=\log N+1\),所以可以省却一个位与运算。
  2. 函数popcount_dnq1的第一行(代码段行号4)还有另一种写法,可以减少一次算术运算。其依据是下面的“种群统计”数学公式3\[\operatorname{popcount}(n)=n-\Bigl\lfloor{\frac{n}{2}}\Bigr\rfloor-\Bigl\lfloor\frac{n}{4}\Bigr\rfloor-\cdots-\Bigl\lfloor\frac{n}{2^{N-1}}\Bigr\rfloor\tag{1}\] N为整数n的比特位数目,\(\lfloor\space\rfloor\)为向下取整操作。此公式的前两项可以用来并行计算宽度为2的比特位段,以一个四比特位数为例: \[\begin{align} n&=a_3⋅2^3+a_2⋅2^2+a_1⋅2^1+a_0⋅2^0\tag{2}\\ \Bigl\lfloor{\frac{n}{2}}\Bigr\rfloor&=a_3⋅2^2+a_2⋅2^1+a_1⋅2^0\tag{3}\\ \Bigl\lfloor{\frac{n}{2}}\Bigr\rfloor\space\&\space0\mathbf{x}5&=a_3⋅2^2+a_1⋅2^0\tag{4}\\ n-(\Bigl\lfloor{\frac{n}{2}}\Bigr\rfloor\space\&\space0\mathbf{x}5)&=a_3⋅(2^3-2^2)+a_2⋅2^2+a_1⋅(2^1-2^0)+a_0⋅2^0\\ &=(a_3+a_2)⋅2^2+(a_1+a_0)⋅2^0\tag{5} \end{align}\] 显然上式(3)等同于将n右移一位。稍加思考,也可以推断出上式(5)得到就是宽度为2的比特位段计数值。依据这一分析,我们可以重写第一行为n = n - ((n >> 1) & 0x55555555);

综合上述两点,优化后的代码如下:

1
2
3
4
5
6
7
8
9
10
/* Divide-and-Conquer - improved (15 arithmetic operations) */
int popcount_dnq2 (uint32_t n)
{
n = n - ((n >> 1) & 0x55555555);
n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
n = (n + (n >> 4)) & 0x0F0F0F0F;
n = n + (n >> 8);
n = n + (n >> 16);
return n & 0x3F;
}

新的popcount_dnq2函数实现比popcount_dnq1少了5个算术运算操作,速度加快了25%。

还有优化的余地吗?

真的有!有经验的系统程序员都知道,许多现代计算机处理器的设计都支持单条乘法指令。由此把一个数乘以0x01010101,等于将其每个长度为8的比特位段相加求和,结果置于最高的字节中,所以只要右移24位就可以得到我们要的计数值。根据这一点,我们可以得到“分而治之”算法的最优实现版本:

1
2
3
4
5
6
7
8
/* Divide-and-Conquer - final (12 arithmetic operations) */
int popcount_dnq3 (uint32_t n)
{
n = n - ((n >> 1) & 0x55555555);
n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
n = (n + (n >> 4)) & 0x0F0F0F0F;
return (n * 0x01010101) >> 24;
}

它只需要12次算术运算操作就完成任务,真的非常快!

使用GCC编译器特定选项,可以生成混合C代码及对照汇编语言的列表(list)文件,用来验证popcount_dnq3实现的优越性。在运行于Intel处理器的Ubuntu Linux x86-64虚拟机上,执行以下命令:

1
gcc -Wa,-adhln -g -march=native popcount.c > popcount.s

然后打开产生的列表文件popcount.s,找到popcount_dnq2popcount_dnq3相关的部分:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
106:popcount.c    **** int popcount_dnq2 (uint32_t n)
107:popcount.c **** {
...
111:popcount.c **** n = n + (n >> 8);
972 .loc 1 111 16
973 0786 8B45FC movl -4(%rbp), %eax
974 0789 C1E808 shrl $8, %eax
975 .loc 1 111 7
976 078c 0145FC addl %eax, -4(%rbp)
112:popcount.c **** n = n + (n >> 16);
977 .loc 1 112 16
978 078f 8B45FC movl -4(%rbp), %eax
979 0792 C1E810 shrl $16, %eax
980 .loc 1 112 7
981 0795 0145FC addl %eax, -4(%rbp)
113:popcount.c **** return n & 0x3F;
982 .loc 1 113 14
983 0798 8B45FC movl -4(%rbp), %eax
984 079b 83E03F andl $63, %eax
...
117:popcount.c **** int popcount_dnq3 (uint32_t n)
118:popcount.c **** {
...
122:popcount.c **** return (n * 0x01010101) >> 24;
1034 .loc 1 122 15
1035 07e7 8B45FC movl -4(%rbp), %eax
1036 07ea 69C00101 imull $16843009, %eax, %eax
1036 0101

可以看到,popcount_dnq2实现里右移8/16位相加各自有三条指令(行号973、974、976和978、979、981),最后的位与0x3F有两条指令(行号983、984),一共8条指令;而在popcount_dnq3实现中只有两条:一条加载指令movl和一条乘法指令imullpopcount_dnq3完胜!

还有一种以空间换时间的“分而治之”方案,虽然看上去比较无趣,但是其执行效率却可与上面的其他算法比肩。这种解决方案预设一个256项的数组,填入0~255之间每个数的比特位计数值,之后对于输入的整数依次取出单个字节查表,然后将结果相加。以下是无比较/分支指令的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const char popcount_tab[256] =
{
0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
};

/* Table lookup method */
int popcount_tablelookup (uint32_t n)
{
return popcount_tab[n & 0xFF] +
popcount_tab[(n >> 8) & 0xFF] +
popcount_tab[(n >> 16) & 0xFF] +
popcount_tab[(n >> 24)];
}

透彻掌握本节的内容,一定可以让面试官对你刮目相看,因为你写出的代码,实现的就是广为认可的高效算法。不信去下载GCC最新的11.1.0版本,看看库文件libgcc/libgcc2.c里的比特位计数函数(复制如下),与前面的代码实质上是一样的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int
__popcountSI2 (UWtype x)
{
/* Force table lookup on targets like AVR and RL78 which only
pretend they have LIBGCC2_UNITS_PER_WORD 4, but actually
have 1, and other small word targets. */
#if __SIZEOF_INT__ > 2 && defined (POPCOUNTCST) && __CHAR_BIT__ == 8
x = x - ((x >> 1) & POPCOUNTCST (0x55));
x = (x & POPCOUNTCST (0x33)) + ((x >> 2) & POPCOUNTCST (0x33));
x = (x + (x >> 4)) & POPCOUNTCST (0x0F);
return (x * POPCOUNTCST (0x01)) >> (W_TYPE_SIZE - __CHAR_BIT__);
#else
int i, ret = 0;

for (i = 0; i < W_TYPE_SIZE; i += 8)
ret += __popcount_tab[(x >> i) & 0xff];

return ret;
#endif
}

总结和应用

下表总结比较了本文全部的解法和算法的函数实现:

分类 函数名 方法概要 性能
常规解法 popcount_common1 从右到左单比特扫描 最慢
常规解法 popcount_common2 输入移位单比特扫描
快速解法 popcount_fast1 减一再位与清零最右1,适用较少1 快(非通用)
快速解法 popcount_fast2 加一再位或置位最右0,适用较少0 快(非通用)
快速解法 popcount_fast1_unrolled fast1循环展开(以空间换时间) 更快(非通用)
快速解法 popcount_fast2_unrolled fast2循环展开(以空间换时间) 更快(非通用)
分而治之 popcount_dnq1 位段并行计数合并、递归 快(通用)
分而治之 popcount_dnq2 位段并行计数合并、递归(优化) 更快(通用)
分而治之 popcount_dnq3 位段并行计数合并、递归(最优化) 最快(通用)
分而治之 popcount_tablelookup 单字节查表法(以空间换时间) 最快(通用)

比特位计数当然不仅仅是用来考验面试者的,它广泛应用于信息学、纠错编码和密码学等多个领域。实际上,“种群统计”就是二进制符号数据的汉明重量4。而两个数据比特串的汉明距离,就定义为二者对应位置上不同比特的个数,即二者相异或后的汉明重量。基于汉明距离的分析是密码分析学的一个关键技术,是历史上破解许多密码的关键。从比特位计数的算法,也衍生出一些快速计算汉明距离的算法,感兴趣者可以留言讨论。

事实上,比特位计数是如此重要,乃至GCC和Clang编译器都提供了内建库函数__builtin_popcount。Intel、AMD和ARM处理器也都为之设定了专门的指令。如下在运行于Intel处理器的Ubuntu Linux x86-64虚拟机上,指定GCC选项-march=native__builtin_popcount函数编译成单一指令popcntl

1
2
3
159:popcount.c    ****         count = __builtin_popcount(num);
1204 .loc 1 159 17
1205 08b4 F30FB845 popcntl -8(%rbp), %eax

对比特位计数功能应用方面的了解,有助于扩展知识面,会成为面试时的加分项。

完整程序(包含以上所有计数函数及测试代码)和示例列表文件的压缩包在此下载:popcount.tar.gz


  1. Reingold, Edward M., Nievergelt, Jurg, and Deo, Narsingh. Combintional Algorithms: Theory and Practice. Prentice-Hall, 1977.↩︎

  2. 比特位取反操作(~)是一个例外,C语言定义其优先级高于乘除、取余和加减运算。↩︎

  3. 这个公式的证明不难,需要讨论的请在评论区留言。↩︎

  4. 命名于美国数学家理查德·汉明(Richard Hamming),他对计算机和通信工程贡献突出。↩︎