基于位运算的 O(loglogn) popcount 算法详解

· · 算法·理论

更快的 \operatorname{popcount}

P1 算法

考虑 \mathcal{O}(\log n) 做法，以 x\in[0,2^{16}) 为例：

\operatorname{popcount}(x) = \sum_{i=0}^{15}\operatorname{popcount}(x_{i})\\ x_i = x \operatorname{and} 2^i\\ \operatorname{popcount}(x_{i}) = \lfloor\frac{x_i}{2^i}\rfloor

注意到，\operatorname{popcount}(x_{i}) 可作如下转化：

\bigg\lfloor\frac{1}{2^{i \operatorname{and} 2^3}}\times \Big\lfloor\frac{1}{2^{i \operatorname{and} 2^2}}\times \big\lfloor\frac{1}{2^{i \operatorname{and} 2^1}}\times \lfloor\frac{1}{2^{i \operatorname{and} 2^0}}\times x_{i}\rfloor\big\rfloor\Big\rfloor\bigg\rfloor

注意到，每次右移运算都要重复 \frac{\log n}{2} 次，有 \log \log n 次右移运算，时间复杂度 \mathcal{O}(\log n \log\log n) 考虑优化重复计算：

统一进行 x >> (i & 1)：

x = (x & 0b0101010101010101) + ((x & 0b1010101010101010) >> 1)

统一进行 x >> (i & 2)：

x = (x & 0b0011001100110011) + ((x & 0b1100110011001100) >> 2)

统一进行 x >> (i & 4)：

x = (x & 0b0000111100001111) + ((x & 0b1111000011110000) >> 4)

统一进行 x >> (i & 8)：

x = (x & 0b0000000011111111) + ((x & 0b1111111100000000) >> 8)

注：在这样的计算顺序下，进位不会影响正确性，但其他（大部分）顺序都会影响，原理可尝试自行分析，测试代码与神秘性质。

在实现时，需注意像是 x = (x & 0b0000000011111111) + ((x >> 8) & 0b0000000011111111) 与 x = (x & 0b0000000011111111) + ((x & 0b1111111100000000) >> 8) 两种写法虽理论效果相同，但实际效果会有不同，一般情况后一种写法会发挥预期效果。

时间复杂度：$\mathcal{O}(\log\log n)$，空间复杂度：$\mathcal{O}(1)$。 ## P2 分析 注意到，在 $x \in [0,2^{16})$ 时，`1,2,4,8` 和 `1,2,8,4` 两种操作顺序都是正确的。类似的，在 $x \in [0,2^{32})$ 时，`1,2,4,8,16`，`1,2,4,16,8`，`1,2,8,4,16` 和 `1,2,16,4,8` 四种操作顺序都是正确的。其原因尚不明确。 下面给出顺序操作的正确性证明： 以 $x\in[0,2^{16})$ 为例： 在进行运算前，可视为 $x_{[0,0]},x_{[1,1]},\dots,x_{[15,15]}$ 分别存储了对应部分数字的 $\operatorname{popcount}$，因为 $\operatorname{popcount}(0)=0,\operatorname{popcount}(1)=1$。 第 $1$ 次运算后，可视为 $x'_{[0,1]},x'_{[2,3]},\dots,x'_{[14,15]}$ 分别存储了对应部分数字的 $\operatorname{popcount}$，因为 $\operatorname{popcount}(x)$ 所占位数不长于 $x$ 所占位数。 第 $2$ 次运算后，可视为 $x''_{[0,3]},x''_{[4,7]},x''_{[8,11]},x''_{[12,15]}$ 分别存储了对应部分数字的 $\operatorname{popcount}$，与上步分析同理。 第 $3$ 次运算后，可视为 $x'''_{[0,7]},x'''_{[8,15]}$ 分别存储了对应部分数字的 $\operatorname{popcount}$，与上步分析同理。 第 $4$ 次运算后，$x''''$ 存储了 $x$ 的 $\operatorname{popcount}$，计算完成。