引入
并行是现实世界中加速计算的基本方法。其中，在 OI 这样的单线程程序中也十分实用的基本操作，就是用单条指令处理多组数据。这种思想中最基本的操作就是位运算，将数据中的一个字[word]看成同时存储和处理多个位的方式。
问题0. 请你自行了解常见的位运算指令的作用。（包括一些 __builtin 等）
并行处理多个位
问题1.1. 输入两个数组 a[32], b[32]，它们分别表示两个二进制数。写一个程序算出 a+ba+ba+b 和 a×ba\times ba×b 的二进制结果数组。中间过程用到的所有变量取值只能为 0/10/10/1，常量不受限制。
问题1.2. 在上面的问题中，我们改为输入 646464 个数组表示的二进制数，并且把中间过程中的每个变量改为 646464 位二进制数，是否可以同时计算 646464 组数的和？
问题2.1. 现在有 nnn 个非负整数（<264<2^{64}<264 ），请你写一个程序算出：对于二进制的每一位，这些数中 111 的个数有多少。令 www（=64=64=64）表示位数（下同），请你写出你算法的时间复杂度。（nnn 远大于 www）
问题2.2. 你能找到这个问题时间复杂度低于 O(nw)O(nw)O(nw) 的方法吗？
模拟 DFA
根据上面的问题，我们可以发现一个基本思路：如果我们能设计出一个所有中间变量取值均为 0/10/10/1 且没有条件判断的算法，显然就可以用位运算并行处理。
问题3. 你在做一个数据结构题，推导之后你发现，每一位信息可以写成一个有 O(1)O(1)O(1) 个状态的 DFA。但是这个问题需要同时计算多个互相独立的位。现在你想用位运算加速。
问题3.1. 如何写一个程序模拟计算一个 DFA 的转移过程，且中间过程用到的所有变量取值都只能为 0/10/10/1？
问题3.2. [BZOJ2908部分] 给出一棵树，树上每个点都有点权，定义树上从 aaa 到 bbb 的费用为树上路径上的点的权值顺次 NAND\operatorname{NAND}NAND（与非）的结果。
NAND\operatorname{NAND}NAND 本身不满足结合律，所以在这个数据结构中我们维护的路径信息是：对每一位分别维护“每种可能输入从左到右依次 NAND\operatorname{NAND}NAND 这一段路径后得到的结果”
你能否用位运算同时处理所有位的信息，而不用枚举每一位？
练习
问题4. 给你 nnn 个非负整数（<264<2^{64}<264 ）的序列，求其所有子区间的按位异或和的和。答案 mod 264\bmod 2^{64}mod264 。（n≤4×107n\leq4×10^7n≤4×107 ）
问题5. 给你 nnn 个非负整数（<264<2^{64}<264 ）的序列，求其所有子区间的按位或和的和。答案 mod 264\bmod 2^{64}mod264 。（n≤4×107n\leq4×10^7n≤4×107 ）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
答案
部分因为作者今天记录较为匆忙，没有代码，可以根据提纲来自己手写代码或者让AI生成。
问题0（只做了解即可）
__builtin_popcount 返回二进制中 111 的个数
__builtin_clz 返回二进制中前导 000 的个数
__builtin_ctz 返回二进制中尾缀 000 的个数
__builtin_parity 返回二进制中 111 的个数奇偶性
__builtin_ffs返回二进制中最低位 111 的位置
问题1.1&1.2——基本加法乘法模拟（高精度基础）
323232 位和 646464 位的差不多，最多改个数组大小，这里以 646464 位自然溢出为例：
只不过，64个数组并行加法的时候进位可能不只是一个布尔类型变量，而是一个长度约为 666 的布尔数组，但逻辑上类似
不过还有一个做法：{an}\{a_n\}{an } 数组在二进制下，从低到高，每个数的第一位写为 x0x_0x0 ，每个数的第二位写为 x1x_1x1 ，依此类推；
{bn}\{b_n\}{bn } 数组在二进制下，从低到高，每个数第一位写为 y0y_0y0 ，第二位写为 y1y_1y1 ，依此类推。
这样，可以把 {an}\{a_n\}{an } 与 {bn}\{b_n\}{bn } 的元素逐一相加变为几个二进制数组相加。
当然，这里看似没有用，但是接下来这种想法会有助于我们完成问题2。
问题2.1
正常想到的暴力思路就是 O(nw)O(nw)O(nw) 的时间复杂度，暴力拆出每一位，然后进行统计
问题2.2
可以像刚才一样的过程，列出这 nnn 个数的二进制每一位，记作 x1,x2,⋯x_1,x_2,\cdotsx1 ,x2 ,⋯，这样，只需要像前面一样，横向处理会快捷很多。
当然，速度还可以更快，像启发式合并一样，原本像 (((x1+x2)+x3)+x4)(((x_1+x_2)+x_3)+x_4)(((x1 +x2 )+x3 )+x4 ) 一样的操作，现在改为 (x1+x2)+(x3+x4)(x_1+x_2)+(x_3+x_4)(x1 +x2 )+(x3 +x4 )，这样子，每次加法的时候进位会少很多，因而时间复杂度会降低。其时间复杂度为：
O(∑i=1n=n2i×i)\displaystyle O(\sum_{i=1}^{n}=\dfrac{n}{2^i}\times i)O(i=1∑n =2in ×i)
利用放缩可以得到，O(n)=O(∑i=1nn2i)≤O(∑i=1nn2i×i)≤O(∑i=1nn2i×1.5i)=O(∑i=1nn⋅(34)i)=O(3n)∼O(n)\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)O(n)=O(i=1∑n 2in
)≤O(i=1∑n 2in ×i)≤O(i=1∑n 2in ×1.5i)=O(i=1∑n n⋅(43 )i)=O(3n)∼O(n)
因而，其时间复杂度渐进等价于 O(n)O(n)O(n)。
问题3.1——模拟DFA
> DFA：一个程序拥有固定几种状态，每次输入一个新的字符，根据当前状态和新字符进行一个确定的转移的过程叫做DFA
设状态数位 nnn，直接开 nnn 个 0/10/10/1 变量，第 iii 个表示在不在第 iii 个节点，这样每个 0/10/10/1 取值可以和它下一个位置用位运算进行关联。
当然，读入字符也全变为 0/10/10/1 向量。
由于处理较小的自动机，因而我们模拟过程中代价也是常数。相当于在正确的位置时 111，其它都是 000，从存确切数字变为存储向量
问题3.2——NAND\OPERATORNAME{NAND}NAND
原题：书上路径，处理方式：树链剖分
题意：查询区间从左往右 NAND\operatorname{NAND}NAND 的结果。
输入为 0/10/10/1，进入 fff 函数时输出只可能是 f0/f1f_0/f_1f0 /f1 ，因而可以利用转移到 0/10/10/1 的系数利用矩阵乘法进行优化。
例如，本来矩阵乘法为 Ci,j=∑1≤k≤nAi,k×Bk,j\displaystyle C_{i,j}=\sum_{1\leq k\leq n} A_{i,k}\times B_{k,j}Ci,j =1≤k≤n∑ Ai,k ×Bk,j
现在，只需要把它变为 \displaystyle C_{i,j}=\or_{1\leq k\leq n}A_{i,k}\and B_{k,j}
问题4
前缀异或和，问题转化为 ∑0≤i<j≤nprexor[i]⊕prexor[j]\displaystyle\sum_{0\leq i<j\leq n}prexor[i]\oplus prexor[j]0≤i<j≤n∑ prexor[i]⊕prexor[j]，利用问题2的方法优化时间复杂度
问题5
某一位按位或和为 000 的区间，只可能是这一位全为 000 的区间，因而只需要对于每一位分别统计这一位上每一段连续 000，计算它们这一段长的平方和。
接下来还是利用问题2的思路，设区间长度为 LLL，当前位的后一位为 ccc，取 !c!c!c，然后让 L=L+(!c)L=L+(!c)L=L+(!c)，并让 LLL 的每一位 \and(!c)，这样只有 log(n)\log(n)log(n) 次操作，
不过，时间还会爆炸，因而，需要用到前面所说的启发式合并式操作，维护区间端点是 0/10/10/1，然后合并。
总之，它必然可以转换成纯粹的位运算。
记上一区间首位为 L1,R1L_1,R_1L1 ,R1 ，值为 s1,e1s_1,e_1s1 ,e1 ，下一区间首位为 L2,R2L_2,R_2L2 ,R2 ，值为 s2,e2s_2,e_2s2 ,e2 ，可以理解为贡献为 (R_1\times L_2)\and e_1\and s_2
这里唯一的难点就是乘法，不过乘法已经在问题1中解决，因而时间复杂度只有 O(w2)O(w^2)O(w2)，又因为位数只是段长，所以时间复杂度为 O(log2L)O(\log^2L)O(log2L)
总结 - OI卡常优化：
将 if 判断语句改为固定电路，一定有这样满足要求的手法能够进行这样的计算。本来是数组，现在是存储其每个数的第 iii 位，并行这么多数的计算，在某些问题中能够起到优化作用
名师建议：一般只用来卡常优化，需要在复杂度除以 www 的时候用。比如你发现时间复杂度奔着线性去的时候去用。（当然，你故意乱搞的情况下除外。）
在NOIP阶段举出一个例题较为困难，因此只做了解即可。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
声明
这个是某位著名OI老师的思考题，作者只是作为转载，可能有记录错误，还请见谅。
