更好的 popcnt

眾所周知 $\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 後兩個方法耗時都差不多。