二进制位运算

Published: August 23, 2019 by Daltao

• Categories:
• algorithm 101

• Tags:

• 位运算典型问题
• 加法和位运算的转换
• 二进制运算的合并
• 亦或归0问题
• 二进制优化-bitset
• 二进制优化-偏序关系
• 二进制求和

位运算典型问题

给定一个序列$a_1,a_2,\ldots,a_n$，满足$0\leq a_i < 2^k$，其中$k\leq 20$，$n\leq 2^k$。

问题1：要求找到两个不同的下标$i\neq j$，使得$a_i \& a_j$最大。

这个问题的经典做法就是维护一颗二叉树，之后遍历整个序列，当处理$a_i$的时候，我们先进入二叉树贪心搜索与它且最大的数，之后将$a_i$也插入到二叉树中。整体的时间和空间复杂度为$O(nk)$。

问题2：要求找到两个不同的下标$i\neq j$，使得$a_i \mid a_j$最大。

很显然， $a_i | a_j\geq \max(a_i|a_i,a_j|a_j)$ ，因此$i\neq j$的约束可以无视。 我们需要建立一个数组$B$，其中 $B[i]$ 表示的是序列a中i的二进制超集的数目。这个我们可以利用快速沃什尔变换得到。 之后对于每个数$a_i$，我们从最高比特开始枚举到最低比特，二分判断当一个数为$a_i$时，可以通过或运算得到最大的数是什么。 这个算法的时间复杂度为$O(k2^k)$，空间复杂度为$O(2^k)$。

问题3：要求找到两个不同的下标$i\neq j$，使得$a_i \oplus a_j$最大。

这个做法同且运算，也是维护一颗二叉树，遍历序列，贪心找最大。整体的时间和空间复杂度为$O(nk)$。

问题4：要求找到两个不同的下标$i\leq j$，使得$a_i \oplus a_{i+1} \oplus \ldots \oplus a_j$最大。

首先我们维护一个新的序列$b_0,b_1,b_2,\ldots, b_n$，其中$b_0=0$，且$b_i=b_{i-1}\oplus a_i$。那么原问题中任意连续区间的亦或和都满足 $a_i \oplus a_{i+1} \oplus \ldots \oplus a_j=b_{i-1}\oplus b_j$ ，因此现在的问题就变成了在序列$b$中找两个数令其亦或值最大，同问题3。

问题5：要求找到$a$的某个子序列（子集），使得子序列中的所有数的亦或和最大。

线性基裸题。时间复杂度为$O(nk)$。

问题5：要求找到$a$的某个子序列（子集），问可以得到多少不同的亦或和

线性基裸题。时间复杂度为$O(nk)$。

问题5：要求找到$a$的某个子序列（子集），问所有可以得到的亦或和中第k小的亦或和

线性基裸题。时间复杂度为$O(nk)$。

问题7：要求将序列$a$分成非空两部分，记两部分的亦或和分别为$x$和$y$，要求$x+y$最大

设两部分分别为$B={b_i}$和$C={c_i}$。分别记大小为$l$和$t$。

由于$x+y=x\oplus y+2\cdot (x\&y)$，而$x\oplus y$是固定的，因此我们需要让$x\&y$最大化。考虑到$x\&y\geq 0$，因此题目中$B$和$C$非空的约束可以忽略。

考虑如果在原序列$a$中，第$i$比特位之和为奇数，那么$x\&y$的第$i$比特一定是0。因此我们将这些和为奇数的比特删除也不会影响$x\&y$的值。之后仅剩下为偶数的比特位，考虑到此时一定有$x=y$，因此我们只需要让$x$最大即可。

我们现在面临的问题是，从修正后的序列（删除和为奇数的比特后）中，挑选一些数值，令其亦或和最大。这个问题实际上就是问题5，用线性基处理一下就好了。

问题8：要求在$a$序列中选择两个不同的元素$x$和$y$（值允许相同），要求$x$与$y$进行二进制且运算后包含最多的1。

这问题实际上要求我们找到某个特殊的数$t$，使得$t$的超集在序列$a$中出现不少于两次。一种简单的方式就是直接统计$0$到$2^k-1$中每个数的超集在序列中出现次数，这个可以直接通过快速沃什尔变换以$O(k2^k)$的时间复杂度计算得到。之后找到这个数$t$后，扫描一遍序列，从中任意拎两个$t$的超集出来。

总的算法时间复杂度为$O(k2^k+n)$

问题9：要求在$a$序列中选择两个不同的元素$x$和$y$（值允许相同），要求$x$与$y$进行二进制或运算后包含最多的1。

这里的不同是没有意义的，因为要或运算后包含最多的1，那么必定会选择两个不同的值。

我们可以这样求解，维护一个特殊的数组$b$，$b_i$记录序列$a$中与$i$进行且运算后包含最多$1$的数。这个数组可以这样求，首先对于任意序列中的数$a_i$，很显然与$b_{a_i}=a_i$。之后我们可以进行下推操作，将$b_i$中的数下推给所有$b_j$，其中$j\in i$。之后我们再进行一次上推操作，将每个数$b_i$上推给自己的超集。

上面这个算法看起来应该是$O(3^k)$，但是我们可以仅枚举恰好比当前集合小1和大1的子集或超集，就可以将时间复杂度降低为$O(k2^k)$。

现在我们要找或运算后拥有最多1的家伙了，直接暴力遍历每个序列$a$中的值，记现在的$a_i$，那么要找与$a_i$或运算后含最多$1$的数，实际上就是在找$b_{(2^k-1)\oplus a_i}$，其中$\oplus$表示亦或运算。

总的算法时间复杂度为$O(k2^k+n)$

问题10：要求在$a$序列中选择两个不同的元素$x$和$y$（值允许相同），要求$x$与$y$进行二进制亦或运算后包含最多的1。

我没有特别好的解法，不知道别人有没有，我只想出了一个$O(k2^k+3^k)$的算法。

我们可以保留问题9中的数组$b$，只是修改一下定义，$b_i$记录序列$a$中$i$的超集中，拥有最少$1$的数。这样的话，我们的下推操作还是可以执行的，时间复杂度为$O(k2^k)$。

但是在真正计算结果的时候，我们对于每个$a_i$，我们要找到$((2^k - 1)\oplus a_i)$的所有子集$j$，并尝试$a_i$与$b_j$的组合。这样的话这一段的总的时间复杂度为$O(3^k)$。

问题11：要求在$a$序列中选择两个不同的元素$x$和$y$（值允许相同），要求$x$与$y$进行二进制且运算后包含最多的0。

问题8要求包含最多的1，这个问题要求包含最多的0，由于1的数目和0的数目的和是常数，因此问题实际上要求我们包含最少的1。

要解决这个问题，需要注意到或运算和且运算的不同，或运算仅在两个数都为0的时候返回0，而且运算仅在两个数都为1的情况下放回1，因此我们可以利用这个性质。事实上下面公式是恒成立的：

$x\land y = \lnot(\lnot x\lor \lnot y)$

因此我们可以直接将所有序列$a$中的二进制位取反，之后利用问题9去寻找或运算后包含最多1的两个数即可。

问题12：要求在$a$序列中选择两个不同的元素$x$和$y$（值允许相同），要求$x$与$y$进行二进制或运算后包含最多的0。

同问题11，只要将所有序列$a$中的二进制位取反，之后利用问题8去寻找且运算后包含最多1的两个数即可。

问题13：给出m个请求，第$i$个请求给定$l_i$和$r_i$，要求在$a_{l_i},\ldots,a_{r_i}$中挑选两个数，使得两个数且运算后拥有最多的1。这个问题额外满足下面条件：$l_i<r_i$，$a_i$最多包含$8$个1，$m\leq 5\cdot 10^6$。

首先我们定义一个特殊的函数$f$，$f(i,j)$表示仅考虑前$i$个数，值是$j$的超集的最靠右的数的下标。同时我们需要定义另外一个辅助函数$g$，$g(i,j)$表示仅考虑前$i$个数中，所有答案为$j$（在最优策略下取出的两个数且运算后含有$j$个1）的区间的最大左边界。

从左到右处理所有的$a$中元素，就可以很简单的处理出$f$和$g$，而且需要注意的是我们可以直接在$f(i-1,j)$上进行修改得到$f(i,j)$，换言之我们可以复用之前的数据。预处理的时间复杂度为$O(2^8n)$。

下面我们考虑如何处理每个请求，我们注意到对于请求$i$，注意到$g(i,k)$随着$k$的增大而变小，因此我们可以进行二分，但是实际上我们可以直接提前排序请求，这时候按序遍历一次即可。要处理所有右边界为$i$的请求，我们只需要遍历一次k，同时按照左边界从大到小遍历一遍请求即可，总的时间复杂度为$O(M_i+8)$，这里$M_i$表示右边界为$i$的请求数。

整体的时间复杂度为$O((8+2^8)n+2^k+m\log_2m)$。还是非常快的。

问题15：给出m个请求，第$i$个请求给定$l_i$和$r_i$，要求在$a_{l_i},\ldots,a_{r_i}$中挑选两个数，使得两个数亦或运算后拥有最少的1。这个问题额外满足下面条件：$l_i<r_i$，$a_i$最多包含$8$个1，$m\leq 5\cdot 10^6$。

定义$f(i,j,k)$表示仅考虑前$i$个数，$j$的所有超集中比$j$多$k$个二进制1的最靠右的数的下标。而$g(i,j)$表示仅考虑前$i$个数，答案为$j$的所有区间最大的左边界。

之后从左往右计算两个函数即可，计算函数的同时顺便把请求都回答了。

总的时间复杂度为$O((8+2^8)n+8\cdot 2^8+m\log_2m)$

提供一道题目。

问题16：给定一个序列$a_1,a_2,\ldots, a_n$，要求统计有多少不同的下标对$(i,j)$，满足$i\leq j$且$a_i \& a_j=0$。满足$n\leq 10^6, a_i< 2^{k},k=18$

首先$0$比较麻烦，我们把0先提取出来独立处理掉，时间复杂度为$O(n)$。

下面说一下暴力枚举子集的做法：

现在序列中不存在0了，我们用$c(x)$表示$x$这个数字出现的次数。任意两个数且运算位0，这意味着两个数的或运算结果恰好是二者的和。现在我们考虑有多少下标对$(i,j)$，满足$a_i\&a_j=0$且$a_i+a_j=m$。我们可以直接尝试将$m$拆分成两部分$a,b$，满足$a<b$且$a\&b=0$且$a+b=m$，对于每个对将$c(a)c(b)$贡献到结果中。

上面的枚举$a$一旦确定，$b$也随之确定了，$a$可能是所有$m$的子集，而$0$到$2^k-1$之间的所有子集的总数是$3^k$。因此算法的时间复杂度为$O(3^k+n)$，结果的常数为$\frac{1}{2}$，实际的计算量不超过2亿次。

再说一个用快速沃什尔变换的方法。对于$0$到$2^{k}-1$，我们统计每个数的子集数目，这个可以通过快速沃什尔变换以时间复杂度$O(k2^k)$得到。记$s(x)$表示$x$的子集数目。

接下来我们逐一处理每个数，假设现在在处理$x$，与其且运算结果为$0$的数有$s(x\oplus (2^{k}-1))$。

需要注意的是上面的方式每次统计，每个数对都会贡献两次，所以这部分结果最终需要除去2。

这种方法的总的时间复杂度为$O(k2^k)$。

题目17：给定一个序列$a_1,\ldots,a_n$，问有多少不同的区间$l,r$，满足$a_l\oplus\ldots \oplus a_r>\max(a_l,\ldots,a_r)$。

由于要找区间最大值，这个太麻烦了，我们可以在序列上建立笛卡尔树，以值最大的数作为根（多个值最大任选一个）。之后遍历笛卡尔树。在考虑某个子树的时候，我们统计覆盖根的所有有效区间。我们发现区间最大值是根，因此只要保证比根大即可。

我们先特殊处理每个数，处理出前缀亦或和，这样区间亦或就变成了两个数之间的亦或。之后我们要分别从左右孩子中找到一个数，使其亦或后比根大。这个可以通过为左右子树建立一个二叉树，将每个数的二进制形式保存进去。之后递归遍历两颗子树的二叉树即可，这样可以证明每次遍历仅较小的树会被完全遍历，因此时间复杂度为$O(n\log_2M\log_2(n\log_2M))$，而合并的时候每次都会删除一个顶点，因此整体的时间复杂度为$O(n\log_2M)$。最后总的时间复杂度为$O(n\log_2M\log_2(n\log_2M))$。

题目18：给定一个序列$a_1,\ldots,a_n$，问有多少不同的区间$l,r$，满足$a_l\lor \ldots \lor a_r>\max(a_l,\ldots,a_r)$，这里$\lor$表示二进制或

先建立一颗笛卡尔树，之后对每颗子树统计覆盖根的有效区间数。由于根是最大值，区间中至少要覆盖另外一个数，不是根的子集。我们可以提前为每个数预处理出前驱和后继的非子集数的下标。这个可以$O(n\log_2M)$完成。

之后我们发现要覆盖区间，要么左边界要小于等于前驱，要么有边界要大于等于后继，容斥就可以了。

时间复杂度为$O(n\log_2M)$。

问题19：给定一个序列$a_0,\ldots,a_{n-1}$，其中$n=2^k$。要求计算所有$f(x)$，其中$1\leq x\leq n-1$，其中$f(x)=\max_{i,j\in x\land i\neq j}a_i+a_j$。

这个问题，我们可以直接用枚举子集来解决，时间复杂度为$O(3^k)$。但是我们实际上可以以$O(k2^k)$来解决这个问题。

记$dp(i,j)$表示所有$x$满足，$x\in i$且$x$拥有与$i$相同的低$j$位，由$a_x$组成的元素的集合。

可以发现对于$j$，如果$i$的第$j$位为$0$，则有$dp(i,j-1)=dp(i,j)$。否则如果$i$的第$j$位为1，其集合中的元素要么第$j$位为$1$，要么为$0$。因此$dp(i,j-1)=dp(i-2^j,j)\cup dp(i,j)$。

上面的集合中我们只需要维护最大的两个元素就行了，因此上面提到的并集操作可以$O(1)$完成。

总的时间复杂度为$O(k2^k)$。

提供一道题目。

问题20：给定两个集合$A$和$B$，每个集合初始的时候各包含一个整数$0$。之后执行$m$次操作，每次操作向$a$或$b$增加一个新元素$x$。要求每次操作或输出$\max_{a\in A,b\in B}bitcount(a\& b)$，其中$\&$表示二进制且运算，$bitcount$统计一个整数的二进制形式中$1$的数目。其中$1\leq m\leq 10^6,0\leq x\leq 2^{20}$。

对于每个集合我们维护一个辅助数组$set$，其中$set(i)$表示$i$的任意超集是否加入到集合中。当加入一个新的数$x$的时候，我们可以枚举$x$的子集并加入。假如直接这个做会导致维护$set$的时间复杂度达到$O(3^{20})$，这里可以用一个技巧，就是我们加入$x$后之后在加入比$x$正好少一个$1$的子集，这样时间复杂度就优化到了$O(20\cdot 2^{20})$。

最后拥有最多的$1$的两个整数的且的结果，我们记作$core$，很显然$A$和$B$的$set(core)$都被设置为$1$了。我们可以在计算$set$的时候就实时维护拥有最多$1$的在两个$set$中都被设置为$1$的下标即可。

所以总的时间复杂度为$20(m+2^{20})$。

提供一道题目。

题目21：给定两个序列$a_1,\ldots,a_n$和$b_1,\ldots,b_n$，给定$m\leq n$，要求计算$\max_{i\leq j}bitcount(a_i\& b_j)$。其中$1\leq n,a_i,b_j\leq 10^6=M$

这个问题可以这样解决。记$L(x)$表示最小的$i$，满足$x\subseteq a_i$，而记$R(x)$表示最大的$j$，满足$x\subset b_j$。因此结果就变成了$\max_{x}bitcount(x)[L(x)\leq R(x)]$。而$L(x)$和$R(x)$都可以$O(M\log_2M)$计算。只需要学习问题20的方式维护一个core即可。

总的时间复杂度为$O(M\log_2M)$。

加法和位运算的转换

问题1：在区间$[L,R]^2$中有多少个整点$(a,b)$，满足$a+b=a\oplus b$

这个问题非常简单，只需要了解：$a+b=a\oplus b + 2(a\&b)$。因此问题的实际意思是问区间有多少对数$a$，$b$，满足二者的且运算结算没有1。这个数位DP即可。

问题2：在区间$[L,R]^2$中有多少个整点$(a,b)$，满足$a+b=a | b$

依旧很简单，只需要了解：$a+b=a | b + a\&b$。因此问题的实际意思是问区间有多少对数$a$，$b$，满足二者的且运算结算没有1。这个数位DP即可。

问题3：在区间$[L,R]^2$中有多少个整点$(a,b)$，满足$a\oplus b=a | b$

还是很简单，只需要了解：$a|b=a+b-a\&b=a\oplus b+a\&b$。因此问题的实际意思是问区间有多少对数$a$，$b$，满足二者的且运算结算没有1。这个数位DP即可。

问题4：给定两个长度分别为$n$和$m$的序列$A=a_1,\ldots,a_n$与$B=b_1,\ldots,b_m$，要求计算$\oplus_{i,j}(a_i+b_j)$。

这类问题的做法就是逐位讨论，因此我们下面说的算法需要运行$O(30)$次。

现在考虑第$k$位的值，我们考虑每个数低$k$位二进制形式，那么$(a_i+b_j)$会对结果产生影响当且仅当$a_i$与$b_j$在第$k$位拥有相同的值，但是低$i-1$相加后有进位，或者$a_i$与$b_j$在第$k$位拥有不同的值，但是低$i-1$相加后无进位。

如果我们将$A$和$B$按照后$k$位进行排序，就可以用双指针技术线性求解第$k$位的贡献。假如我们这里使用基数排序，那么处理每一位的时间复杂度就是线性的了。

总的时间复杂度为$O(n\log_2n)$。

题目5：给定三个非负整数$a,b,c$，要求找到一个最小的非负整数$x$，满足$(a-x)\oplus (b+x)\oplus c=0$，且要求$x\leq a$。如果无解输出$-1$，其中$0\leq a,b,c\leq 10^{15}$

问题等价于找到两个数$A$和$B$，满足$A\leq a$且$A+B=a+b$且$A\oplus B=c$，并且我们希望$A$尽可能大。我们将加法公式展开得到：

$$a+b=A+B=A\oplus B+2(A\&B)$$

借之我们可以推出$A\&B=(a+b-c)/2$。之后我们可以枚举$c$的二进制中的$1$，从高到低枚举，并贪心加在$A$上即可。

这个问题告诉我们的是一旦出现两个约束条件，我们可以的到第三个约束条件，从而求解答案。

二进制运算的合并

• $(a\land b)\lor (a\land c)=a\land (b\lor c)$
• $(a\lor b)\land (a\lor c)=a\lor (b\land c)$
• $(a\land b)\oplus (a\land c)=a\land (b\oplus c)$
• $(a\lor b)\oplus (a\lor c)=\lnot a\land (b\oplus c)$

亦或归0问题

序列版本：给定一个序列$a_1,a_2,\ldots, a_n$，保证$a_1\oplus a_2 \oplus \ldots \oplus a_n=0$，且$a_i<16$。现在我们希望通过下面操作将整个序列中每个数都化作0：

每次操作，你都可以任意选择两个不同的下标$1\leq i<j\leq n$，之后选择任意一个非负整数$x$，并用$a_i\oplus x$替换$a_i$，$a_j\oplus x$替换$a_j$。

问最少需要多少次上面所说的操作才能达成目标。

如果我们对$i$和$j$执行了一次上面的操作，可以发现$a_i\oplus a_j$在操作前后是不变的。我们可以在$a_i$和$a_j$之间连一条边。

考虑通过这些边形成的一个连通块，连通块中每个数可以化为0当且仅当连通块中所有数的亦或和为0。（事实上连通块是一株树，直接在树上dfs即可得到一组方案）

接下来问题就是我们希望使用最少的边，连接一些不连通的连通块，使得每个连通块中数值的异或和为0。

设m是连通块数目，E是使用的边数，那么有等式$n-E=m$成立。因此要让边最少，等价于让连通块的数量最多。

现在考虑如何让连通块的数量最多。

可以证明数值为0的顶点v一定单独形成一个连通块，否则我们从它所在的连通块中可以分离出v，得到更多的连通块。同时如果两个数值相同的顶点u、v存在，那么我们可以始终连接它们两个形成独立的连通块，这样依旧能保证得到的结果中连通块最多在这个性质。（比如u、v在不同连通块中，则从两个连通块中删除这两个顶点，并将u、v连边，同时将两个连通块连边即可，这样连通块的总数不变）。

因此通过上面这个过程，我们可以解决一部分顶点，之后每个数值$x$，$1\leq x\leq 15$，我们最多都只剩下一个顶点。我们可以直接在上面进行位压DP即可，总的时间复杂度为$O(3^{16}+16\cdot 2^{16})$。

树上版本：给定一株树拥有n个顶点的树，树上的边有边权（边权小于16）。我们希望通过执行若干次下面操作，将每条边的权重变为0：

每次操作，你都可以任意选择两个顶点以及一个非负整数$x$，并将两个顶点决定的简单路径中所有的边的权重都亦或上$x$。

问最少需要多少次上面所说的操作才能达成目标。

我们可以将每个顶点的值设置为与它相连的边的权重的亦或和。那么原来操作等价于选择两个顶点，将两个顶点的值亦或上x。

可以证明树上所有边的权重都化为0，当且仅当树上所有顶点的值都化作了0（叶顶点的值为0，当然连它的唯一边的权值也是0，可以用归纳法证明其它情况）。

因此问题等价于有一个值序列，我们每次操作都选择两个值亦或上x，直到序列所有数都为0，这就是序列版本的亦或归0问题。

题目链接

问题1：给定$n$个非负整数$a_1,\ldots,a_n$，要求将每个数加上另外一个非负整数$x_1,\ldots,x_n$，满足$\oplus_{i=1}^n(a_i+x_i)=0$且$\sum_{i=1}^nx_i$最小。其中$1\leq n\leq 10^5$，$0\leq a_i\leq 10^{18}$

如果$\oplus_{i}a_i=0$，那么答案一定是$0$。

先考虑$n$是偶数的情况。设$\oplus_{i}a_i$的最高位为第$b$位，那么我们可以认为所有$a_i$的最高位都不超过$b$（超过的部分设为$0$显然不影响结果）。我们必须将某个第$i$位为$0$的数增大到$2^i$（为啥不将第$i$位为$1$的数增大到$2^{i+1}$呢，因为我们必须将偶数个数都做这种操作，但是这无法解决第$i$个数有奇数个$1$的问题）。选哪个数呢，可以发现我们始终可以选择满足条件的最大的数，为啥，设有两个数$x,y$满足条件，且$x<y$，我们选择将$x$增大到$2^i$的过程中，会需要先将$x$增大到$y$，这时候我们可以选择将原先的$y$增大到$2^i$，但是这明显不如保留$x$，直接将$y$增大到$2^i$。于是乎这里给出了一个$O(n\log_2M)$的贪心算法，其中$M$为数据范围。

但是问题还没解决，考虑$n$为奇数的情况，同样设$\oplus_{i}a_i$的最高位为第$b$位。这时候可能存在一种非常特殊的情况，就是所有数的第$b$位都是$1$。这时候我们的贪心算法就不管用了。要将第$b$位的$1$变成偶数，需要将某个$1$提高到第$b+1$位，当然第$b+1$位可能初始也都是$1$。于是乎我们最后必须将$1$提高到第$t$位，但是这会导致第$t$位出现奇数个$1$，因此我们还需要再提一个$1$上去。总结就是我们需要选择某一位$t$，将这一位正好增加两个$1$，而其它位用贪心算法处理。由于第$t$位增加了两个$1$后，就至少有一个数变成$2^{t}$，即后面几位都是$0$，因此就不会再出现各位都是$1$的尴尬情况了（这就是为啥某位增加两个$1$只需要做一次的原因，同时也不需要增加$4$个$1$或更多）。

这里顺带一提，为啥不能将某一位$t$增加三个$1$或更多。考虑增加三个$1$的情况，我们可以设增加的数分别为$a,b,c$，且$a<b<c$。那么我们将$c$提高到$2^t$，但是仅将$a$提高到$b$即可，这样我们可以减少$x$的总和，同时满足了每一位的奇偶性要求。

具体的算法就是枚举不执行某位增加两个$1$的操作的费用和每一位都尝试某位增加两个$1$的操作的费用，并选择最小即可。总共要执行$O(\log_2M)$次贪心算法，总的时间复杂度为$O(n(\log_2M)^2)$，相当快。

提供一道题目。

二进制优化-bitset

由于计算机中整数的或运算是一个指令完成的，但是一个整数可以包含多达$64$个二进制位，因此相当于我们用一个指令完成了$64$个二进制位的且、或、非、亦或等运算，相当于常数减少为原来的$\frac{1}{64}$。同时用整数存储二进制位可以节省内存（内存使用率仅布尔变量的$\frac{1}{8}$）。

同时还存在各种$O(1)$统计一个整数中最高位的1，最低位的1，1出现的次数的奇技淫巧。

问题1：给定一副包含$n$个顶点$m$条边的无向图，没有重边和自环，问存在多少个长度为3的简单环。（其中$1\leq n\leq 10^5$，$0\leq m\leq 10^6$）。

经典问题了，为每个顶点维护邻接数组，我们可以用bitset来存储。之后对于每条边的两个端点$a,b$，对两个端点的邻接表做且运算后统计有多少个$1$即可。时间复杂度为$O(\frac{n^2}{64})$。

问题2：给定$n$个物品，第$i$个物品的价格为$a_i$。要求选择一些物品，使得选中的物品的价格不超过$p$，且尽可能大。其中$1\leq n\leq 2000$，$1\leq a_i,p\leq 10^6$

背包问题，记$dp(i,j)$表示用$i$件物品，是否存在某个子集的价格和为$j$。容易发现$dp(i,j)=dp(i-1,j)\lor dp(i-1,j-a_i)$。如果我们将$dp(i,?)$表示为一个二进制序列，则会发现$dp(i,?)=dp(i-1,?)\lor 2^{a_i}dp(i-1,?)$。这可以通过bitset优化常数，于是时间复杂度为$O(\frac{np}{64})$。

二进制优化-偏序关系

二进制能用来表示偏序关系。比如我们设定一个阈值$T$，将小于$T$的值全部替换为$0$，而其余值替换为$1$，这样我们就能将一个偏序序列转换为二进制序列，利用二进制易于处理和优化的特性，我们就能以很快的速度解决问题了。

问题2：给定一个长度为$k$的序列$a_1,\ldots,a_k$，其中每个元素都是长度为$m$的向量。定义两个向量的上合并操作结果为一个新的向量，这个向量的每个维度的值都是原来两个向量在这个维度的值的最大值。对应的定义两个向量的下合并操作为一个新的向量，这个向量的每个维度的值都是原来两个向量在这个维度的值的最小值。接下来给出$q$个请求，分成三类：第一类，对两个已经存在的向量进行上合并操作，得到的新的向量追加到序列尾部。第二类，对两个已经存在的向量进行下合并操作，得到的新的向量追加到序列尾部。第三类请求要求输出某个已存在的元素的某个维度上的值。这里$1\leq k\leq 12, 1\leq m, q\leq 10^5，1\leq a_i\leq 10^9=M$。

暴力计算的时间复杂度为$O(mq)$。会超时。

这种问题一般要求我们按每个维度单独处理。因此我们先在可以假设$m=1$，只需要最终将计算答案的时间乘上$m$即可。

对于$m=1$的情况，我们可以$O(q)$计算出结果。但是这显然太慢了。我们可以通过一些预处理（预处理的时间复杂度不用乘上$m$）来加速。比如我们可以发现整个序列由前$k$个数完全决定，我们可以枚举前$k$个数，并应用所有的请求。这样预处理时间复杂度为$O(M^kq)$，不咋样。但是我们发现前$k$个数的数值本身是没啥意义的，只有他们的大小关系会决定整个序列的外贸。因此我们可以枚举所有的排列，这样时间复杂度为$O(k!q)$，嗯，也不咋样。

这里实际上需要个重要的观察，如果答案为$x$，那么我们将前$k$个数中小于$x$的数设置为$0$，而将前$k$个数中大于等于$x$的数设置为$1$，那么我们在执行了所有前两类操作后，答案一定是$1$。为啥呢，可以通过对操作数目进行归纳证明。

我们发现上面所说的技术，长度为$k$的二进制序列总共有$2^k$种，因此我们只需要对$2^k$个不同的二进制序列进行预处理，时间复杂度为$O(2^kq)$。注意这里由于是二进制，因此取最大值等价于或运算，取最小值等价于且运算，因此我们可以用bitset进行优化，将时间复杂度降低为$O(\frac{2^kq}{64})$。

之后我们预处理出所有二进制，那怎么回答请求呢？我们知道对于每个请求，设其问的是第$i$个向量，第$j$个维度。而答案仅可能是$a_{1,j},\ldots,a_{k,j}$中的一个，我们暴力枚举，并用上面提到的二进制校验技术进行校验即可（也可以用二分，但是意义不大）。每个请求回答所需时间复杂度为$O(k^2)$。

总的时间复杂度为$O(\frac{2^kq}{64}+k^2q)$。

提供一道题目。

二进制求和

题目1：对于$0\leq i\leq 50$，给定$a_i$个$2^i$。现在要求为每个数乘上$-1$或$1$或$0$，要求这些乘积和恰好等于$m$，其中$m$是提前给定的整数。判断是否存在这样的一种分配方案。

很简单，首先我们可以认为所有数都乘上$1$，设得到的值为$M$，那么我们还需要从$M$中减去$M-m$才能保证结果正确。现在的问题就变成了，有$a_i$个数可以取$0$、$2^i$、$2^{i+1}$。而由于这些幂能相互整除，因此我们可以直接贪心选择即可。