更好的 popcnt | EarthMessenger 博客

众所周知 $\mathrm{popcnt}$ 是一个十分常用的算法。

它是用于统计二进制数字中 $1$ 的个数的算法。

暴力算法

容易得到常规做法是 $\mathcal O(n)$ 的。

如下：

unsigned int lowbit(unsigned int x)
{
    return x & (-x);
}

// O(n)
int popcnt1(unsigned int x)
{
    int result = 0;
    while (x)
    {
        x -= lowbit(x);
        result++;
    }
    return result;
}

这太慢了，考虑优化。

分析

我们先只考虑 $1$ 字节的简单情况。

考虑建一个线段树，维护区间 $[l, r]$ 中的 $1$ 的个数，当然我们并不会对其进行区间的修改，也只会查询区间 $[0, 8n]$ （一字节 $8$ 位）中的 $1$ 个数。

比如说数 $(11101001)_2$

\begin{array}{|ccccccccccccccc|} \hline 0 & & 0 & & 0 & & 0 & & 0 & & 1 & & 0 & & 1 \\\hline 0 & & 0 & & 1 & & 1 &|& 0 & & 0 & & 1 & & 0 \\\hline 1 & & 0 &|& 0 & & 1 &|& 0 & & 1 &|& 0 & & 1 \\\hline 1 &|& 1 &|& 1 &|& 0 &|& 1 &|& 0 &|& 0 &|& 1 \\\hline \end{array}

所以只需要对于这个数执行建树操作，再直接返回根节点的值。

首先，我们注意到对于 C++ 的数据类型都是 $8 \times 2^n\ \text{bit}$ ，因此一定可以建成一个满二叉树。

其次，注意到当 $n \ge 1$ 时， $n \le 2^n-1$ ，所以 $n$ 一定可以在长度为 $n$ 的一个二进制数中表示出，因此每一层的建树操作都可以在一个整形变量中完成。

再然后，由于我们只返回根节点的数，类似滚动数组，我们不必保存其他的数，可以至始至终都在一个变量里完成操作。

了解这些性质后，我们便可以完成建树操作了。

对于最底下一层，我们不需要操作，因为当该位为 $1$ 时，有 $1$ 个 $1$ ，为 $0$ 则有 $0$ 个 $1$ （废话）。

接着每向上一层，便错位相加，如下：

\begin{array}{|ccccccccccccc|} \hline a &|& b &|& a &|& b &|& \cdots &|& a &|& b \\\\\hline 10 &|&01 &|&10 &|&00 &|& \cdots &|&00 &|&10 \\\\\hline \end{array}

我们把当前状态分为 $a, b$ 两组，所以我们只需要把所有 $a$ 组的数右移再加上 $b$ 组的数，便得到了下一层的数。

举例：现在我们有 $11101001$ （ $1$ 位 $1$ 节）， $11101001 \\& 10101010 >> 1 = 01010100$ ，再加上 $11101001 \\& 01010101 = 01000001$ 便得到了 $10010101$ 。

最终便可以写出代码了：

// O(lg(n))
int popcnt2(unsigned int x)
{
    x = ((x & 0xaaaaaaaa) >> 1) + (x & 0x55555555); // 0xaa = 10101010, 0x55 = 01010101
    x = ((x & 0xcccccccc) >> 2) + (x & 0x33333333); // 0xcc = 11001100, 0x33 = 00110011
    x = ((x & 0xf0f0f0f0) >> 4) + (x & 0x0f0f0f0f); // 0xf0 = 11110000, 0x0f = 00001111
    x = ((x & 0xff00ff00) >> 8) + (x & 0x00ff00ff);
    x = ((x & 0xffff0000) >> 16) + (x & 0x0000ffff);
    return x;
}

用时

benchmark:
popcnt1() * 1000000000, time = 56.269000s
popcnt2() * 1000000000, time = 6.124000s

题外话

其实开了 -O2 后两个方法耗时都差不多。