优雅地统计二进制数中1的个数

统计二进制数中1的个数

内置位计数功能

C++内置了计算函数。

代码

__builtin_popcount(x);

复杂度分析

• 时间复杂度：$\Theta (1)$。实现方法各异，可以近似认为其时间复杂度为 $\Theta (1)$。
• 空间复杂度：$\Theta (1)$。

移位实现位计数

记 $s = x \oplus y$，我们可以不断地检查 $s$ 的最低位，如果最低位为 $1$，那么令计数器加一，然后我们令 $s$ 整体右移一位，这样 $s$ 的最低位将被舍去，原本的次低位就变成了新的最低位。我们重复这个过程直到 $s=0$ 为止。这样计数器中就累计了 $s$ 的二进制表示中 $1$ 的数量。

代码

while (s)
{
    ret += s & 1;
    s >>= 1;
}

复杂度分析

• 时间复杂度：$\Theta (\log n)$
• 空间复杂度：$\Theta (1)$

Brian Kernighan 算法

在移位实现位计数算法中，对于 $s=(10001100)_2$ 的情况，我们需要循环右移 $8$ 次才能得到答案。而实际上如果我们可以跳过两个 $1$ 之间的 $0$，直接对 $1$ 进行计数，那么就只需要循环 $3$ 次即可。

我们可以使用 Brian Kernighan 算法进行优化，具体地，该算法可以被描述为这样一个结论：记 $f(x)$ 表示 $x$ 和 $x-1$ 进行与运算所得的结果，即 $f(x)=x~\&~(x-1)$，那么 $f(x)$ 恰为 $x$ 删去其二进制表示中最右侧的 $1$ 的结果。

基于该算法，只需要不断让 $s = f(s)$，直到 $s=0$ 即可。这样每循环一次，$s$ 都会删去其二进制表示中最右侧的 $1$，最终循环的次数即为 $s$ 的二进制表示中 $1$ 的数量。

代码

while (s)
{
    s &= s - 1;
    ret++;
}

复杂度分析

• 时间复杂度：$\Theta (\log n)$
• 空间复杂度：$\Theta (1)$。

参考

• Brian W. Kernighan and Dennis M. Ritchie, The C Programming Language (Second Edition)
• Peter Wegner, CACM3, 1960