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

文章作者: sfc9982
版权声明: 本博客所有文章除特別声明外,均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来源 sfc9982 !
  目录