【转载】思考题：位运算加速（一）位并行

FanBoys

2026-07-30 17:13:33

发布于：安徽

12阅读

0回复

0点赞

引入

并行是现实世界中加速计算的基本方法。其中，在 OI 这样的单线程程序中也十分实用的基本操作，就是用单条指令处理多组数据。这种思想中最基本的操作就是位运算，将数据中的一个字[word]看成同时存储和处理多个位的方式。

问题0. 请你自行了解常见的位运算指令的作用。（包括一些 __builtin 等）

并行处理多个位

问题1.1. 输入两个数组 a[32], b[32]，它们分别表示两个二进制数。写一个程序算出 $a+b$ 和 $a\times b$ 的二进制结果数组。中间过程用到的所有变量取值只能为 $0/1$ ，常量不受限制。

问题1.2. 在上面的问题中，我们改为输入 $64$ 个数组表示的二进制数，并且把中间过程中的每个变量改为 $64$ 位二进制数，是否可以同时计算 $64$ 组数的和？

问题2.1. 现在有 $n$ 个非负整数（ $<2^{64}$ ），请你写一个程序算出：对于二进制的每一位，这些数中 $1$ 的个数有多少。令 $w$ （ $=64$ ）表示位数（下同），请你写出你算法的时间复杂度。（ $n$ 远大于 $w$ ）

问题2.2. 你能找到这个问题时间复杂度低于 $O(nw)$ 的方法吗？

模拟 DFA

根据上面的问题，我们可以发现一个基本思路：如果我们能设计出一个所有中间变量取值均为 $0/1$ 且没有条件判断的算法，显然就可以用位运算并行处理。

问题3. 你在做一个数据结构题，推导之后你发现，每一位信息可以写成一个有 $O(1)$ 个状态的 DFA。但是这个问题需要同时计算多个互相独立的位。现在你想用位运算加速。

问题3.1. 如何写一个程序模拟计算一个 DFA 的转移过程，且中间过程用到的所有变量取值都只能为 $0/1$ ？

问题3.2. [BZOJ2908部分] 给出一棵树，树上每个点都有点权，定义树上从 $a$ 到 $b$ 的费用为树上路径上的点的权值顺次 $\operatorname{NAND}$ （与非）的结果。

$\operatorname{NAND}$ 本身不满足结合律，所以在这个数据结构中我们维护的路径信息是：对每一位分别维护“每种可能输入从左到右依次 $\operatorname{NAND}$ 这一段路径后得到的结果”

你能否用位运算同时处理所有位的信息，而不用枚举每一位？

练习

问题4. 给你 $n$ 个非负整数（ $<2^{64}$ ）的序列，求其所有子区间的按位异或和的和。答案 $\bmod 2^{64}$ 。（ $n\leq4×10^7$ ）
问题5. 给你 $n$ 个非负整数（ $<2^{64}$ ）的序列，求其所有子区间的按位或和的和。答案 $\bmod 2^{64}$ 。（ $n\leq4×10^7$ ）

答案

部分因为作者今天记录较为匆忙，没有代码，可以根据提纲来自己手写代码或者让AI生成。

问题0（只做了解即可）

__builtin_popcount 返回二进制中 $1$ 的个数

__builtin_clz 返回二进制中前导 $0$ 的个数

__builtin_ctz 返回二进制中尾缀 $0$ 的个数

__builtin_parity 返回二进制中 $1$ 的个数奇偶性

__builtin_ffs返回二进制中最低位 $1$ 的位置

问题1.1&1.2——基本加法乘法模拟（高精度基础）

$32$ 位和 $64$ 位的差不多，最多改个数组大小，这里以 $64$ 位自然溢出为例：

void add(bool a[64],bool b[64],bool(&ans)[64]){
    bool f=0;
	for(int i=63;~i;i--){
        ans[i]=a[i]^b[i]^f;
        f=a[i]&b[i]|a[i]&f|b[i]&f;
    }
}
void mul(bool a[64],bool b[64],bool(&ans)[64]){
    for(int i=63,k=0;~i;i--,k++){
        bool f=0;
        for(int j=63;~(j-k);j--){
            bool tmp=ans[j-k]^(a[j]&b[i])^f;
            f=a[j]&b[i]&ans[j-k]|a[j]&b[i]&f|ans[j-k]&f;
            ans[j-k]=tmp;
        }
    }
}

只不过，64个数组并行加法的时候进位可能不只是一个布尔类型变量，而是一个长度约为 $6$ 的布尔数组，但逻辑上类似

不过还有一个做法： $\{a_n\}$ 数组在二进制下，从低到高，每个数的第一位写为 $x_0$ ，每个数的第二位写为 $x_1$ ，依此类推；

$\{b_n\}$ 数组在二进制下，从低到高，每个数第一位写为 $y_0$ ，第二位写为 $y_1$ ，依此类推。

这样，可以把 $\{a_n\}$ 与 $\{b_n\}$ 的元素逐一相加变为几个二进制数组相加。

当然，这里看似没有用，但是接下来这种想法会有助于我们完成问题2。

问题2.1

正常想到的暴力思路就是 $O(nw)$ 的时间复杂度，暴力拆出每一位，然后进行统计

int ans[64]={};
for(int i=1;i<=n;i++){
	int pos=63;
	while(a[i]){
		ans[pos]+=a[i]&1;
		a[i]>>=1,pos--;
	}
}

问题2.2

可以像刚才一样的过程，列出这 $n$ 个数的二进制每一位，记作 $x_1,x_2,\cdots$ ，这样，只需要像前面一样，横向处理会快捷很多。

当然，速度还可以更快，像启发式合并一样，原本像 $(((x_1+x_2)+x_3)+x_4)$ 一样的操作，现在改为 $(x_1+x_2)+(x_3+x_4)$ ，这样子，每次加法的时候进位会少很多，因而时间复杂度会降低。其时间复杂度为：

$\displaystyle O(\sum_{i=1}^{n}=\dfrac{n}{2^i}\times i)$

利用放缩可以得到， $\displaystyle O(n)=O(\sum_{i=1}^{n}\dfrac{n}{2^i})\leq O(\sum_{i=1}^{n}\dfrac{n}{2^i}\times i)\leq O(\sum_{i=1}^{n}\dfrac{n}{2^i}\times 1.5^i)=O(\sum_{i=1}^{n}n\cdot(\dfrac{3}{4})^i)=O(3n)\sim O(n)$