统计二进制数中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