专栏文章

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

lluanXiPing_AKed_IOI
算法·理论参与者 3已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@mioxoknj
此快照首次捕获于
2025/12/03 02:50
3 个月前
此快照最后确认于
2025/12/03 02:50
3 个月前
查看原文

更快的 popcount⁡\operatorname{popcount}

P1 算法

考虑 O(log⁡n)\mathcal{O}(\log n) 做法，以 x∈[0,216)x\in[0,2^{16}) 为例：
popcount⁡(x)=∑i=015popcount⁡(xi)xi=xand⁡2ipopcount⁡(xi)=⌊xi2i⌋\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
注意到，popcount⁡(xi)\operatorname{popcount}(x_{i}) 可作如下转化：
⌊12iand⁡23×⌊12iand⁡22×⌊12iand⁡21×⌊12iand⁡20×xi⌋⌋⌋⌋\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
注意到，每次右移运算都要重复 log⁡n2\frac{\log n}{2} 次，有 log⁡log⁡n\log \log n 次右移运算，时间复杂度 O(log⁡nlog⁡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) 两种写法虽理论效果相同，但实际效果会有不同，一般情况后一种写法会发挥预期效果。
xx 长度不同时，做法是类似的。
时间复杂度：O(log⁡log⁡n)\mathcal{O}(\log\log n)，空间复杂度：O(1)\mathcal{O}(1)。

P2 分析

注意到，在 x∈[0,216)x \in [0,2^{16}) 时，1,2,4,8 和 1,2,8,4 两种操作顺序都是正确的。类似的，在 x∈[0,232)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∈[0,216)x\in[0,2^{16}) 为例： 在进行运算前，可视为 x[0,0],x[1,1],…,x[15,15]x_{[0,0]},x_{[1,1]},\dots,x_{[15,15]} 分别存储了对应部分数字的 popcount⁡\operatorname{popcount}，因为 popcount⁡(0)=0,popcount⁡(1)=1\operatorname{popcount}(0)=0,\operatorname{popcount}(1)=1。
第 11 次运算后，可视为 x[0,1]′,x[2,3]′,…,x[14,15]′x'_{[0,1]},x'_{[2,3]},\dots,x'_{[14,15]} 分别存储了对应部分数字的 popcount⁡\operatorname{popcount}，因为 popcount⁡(x)\operatorname{popcount}(x) 所占位数不长于 xx 所占位数。
第 22 次运算后，可视为 x[0,3]′′,x[4,7]′′,x[8,11]′′,x[12,15]′′x''_{[0,3]},x''_{[4,7]},x''_{[8,11]},x''_{[12,15]} 分别存储了对应部分数字的 popcount⁡\operatorname{popcount}，与上步分析同理。
第 33 次运算后，可视为 x[0,7]′′′,x[8,15]′′′x'''_{[0,7]},x'''_{[8,15]} 分别存储了对应部分数字的 popcount⁡\operatorname{popcount}，与上步分析同理。
第 44 次运算后，x′′′′x'''' 存储了 xx 的 popcount⁡\operatorname{popcount}，计算完成。

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...