本文涉及知识点
证明容斥原理和证明集合枚举都用到了：二项式定理
【数学归纳法 组合数学】容斥原理
基础知识
位运算优先级
位运算的结合性都是从左到右。优先级低的先运算。
| 优先级 | 位运算符 | 说明 |
|---|---|---|
| 7 | << >> | 位左移/位右移 |
| 10 | & | 按位与 |
| 11 | ^ | 按位异或 |
| 12 | 按位或 |
注意：不同的编译系统的实现可能不同,所以加上括号保险。就算你把运算顺序牢记于心，你的同事未必记得。
异或（xor ^ )
定义：x1 ⊕ \oplus ⊕x2 = y,对各二进制位分别运算，如果x1和x2的某个二进制位不同（异），则y的此二进制位为1，否则为0。
性质一：
n个数的异或和（积），如果这n个数的某个二进制为1的数量是偶数，则结果的此二进制位是0(偶数个1）；否则结果的此二进制为是1(奇数个1)。现在用数学归纳发证明：
a, {1,1}和{0,0}是偶数个1，结果为0；{1,0},{0,1} 奇数个1，结果为1。
b,假设n个数符合，则n+1个数也符合。将前两个数进行异或运算就符合假设了。
推论一：
根据性质一，可得如下推论：n个数求异或积，可以任意调换数的顺序结果不变。
性质二：
0 ⊕ \oplus ⊕ x = x
性质三：
x ⊕ \oplus ⊕ x = 0
性质四，异或逆运算是其本身：
x1 ⊕ \oplus ⊕ x2 = y ,则 y ⊕ \oplus ⊕ x2 = x1
性质五：
x1 ⊕ \oplus ⊕ x2 <= x1 + x2
如果x1,x2的 所有的二进制位不同时为1,则 x1 ⊕ \oplus ⊕ x2 == x1 + x2
否则： x1 ⊕ \oplus ⊕ x2 < x1 + x2
习题
n双m种筷子， 遗失一只，求遗失的一只长度。m值未知。
已知：2n-1只筷子的长度：{a1,a2 ⋯ a 2 n − 2 , a 2 n − 1 \cdots a_{2n-2},a_{2n-1} ⋯a2n−2,a2n−1 }
思路：根据性质三，答案就是这2n-1的数的异或积。
位与(&)
定义： x1 & \And & x2 = y。对二进制位分别运算，x1和x2的某二进制位全部为1，y对应的二进制位为1；否则为0。
性质一：
n个数依次位与结果为y，如果这n个数的某二进制位全部为1,则y的对应二进制位为1，否则为0。
推论一：
根据性质一，可得如下推论：n个数求与积，可以任意调换数的顺序结果不变。
性质二：
(-1)&x = x
性质三：
x1 & \And & x2 = y <=min(x1,x2)
位或（|）
定义： x1 ∨ \lor ∨ x2 = y。对二进制位分别运算，x1和x2的某二进制位全部为0，y对应的二进制位为0；否则为1。
性质一：
n个数依次位与结果为y，如果这n个数的某二进制位全部为0,则y的对应二进制位为0，否则为1。
推论一：
根据性质一，可得如下推论：n个数求与积，可以任意调换数的顺序结果不变。
性质二：
0 ∨ \lor ∨ x = x
性质三：
x1 ∨ \lor ∨ x2 >= max(x1,x2)
取反（~）
定义：各二进制位0变1,1变0。
位左移（<<)、位右移(>>)
x << n ，相当于x × \times × 2n
x >> n， 相当于 x ÷ \div ÷ 2n
状态压缩
用int mask的二进制位代替一个bool数组v，此数组长度不超过31。第i位为1，表示v[i]=true；第i位为0，表示v[i]=false。
mask&(1<<i) 表示mask第i为1。i ∈ \in ∈[0,31) 最低位i是0。以下操作，只影响第i位，不影响其它位。
如果mask第i位无论是0还是1,设置为1 mask |=(1<<i)
如果mask第i位是无论是1还是0，设置为0 mask &=~(1<<i)
将mask的第一位取反(0变1,1变0)。 mask ^=(1 << i）
子集状态压缩(枚举子集）
从大到小枚举mask的子集，寻找下一个子集，如果sub为0,没有比它小的子集。否则从右到左寻找第一个不为0的位，假定此位是i1，将i1位减1，也就是变成0。i1后面的位取最大，也就是mask的后i1位。
sub-1 ：由于是从大到小枚举，所以(sub-1)比i1高的位和mask一致。
第i1位变成0。
比i1位低的全为1。
故：mask&(sub-1)就是 比sub小的最大子集。
注意：通过此方法枚举maxMask =(1<<n)-1所有子集的子集的时间复杂度是O(3n)。下面利用二项式定理。
0被maxMask 所有子集枚举，共2n次。
有且仅有一个二进位为1的数共有 ( n 1 ) n \choose 1 (1n)个，被2n-1个子集枚举。除当前位必须是1，其它位01皆可。
有且仅有2个二进位为1的数共有 ( n 2 ) n \choose 2 (2n)个，被2n-2个子集枚举。
∑ i : 0 n ( n i ) 1 i 2 n − i = ( 1 + 2 ) n = 3 n 根据二项式定理 \sum_{i:0}^n{n \choose i}1^i2^{n-i}\\ =(1+2)^n = 3^n \quad 根据二项式定理 i:0∑n(in)1i2n−i=(1+2)n=3n根据二项式定理
常见的运算
x是正整数
(x-1) & \And & x :将最低位的1设置成0。
令第i1位是1，如果有多位是1，i1是最小的。
| 比i1高的位 | i1位 | 比第i1第的位 | |
|---|---|---|---|
| x-1 | 和x相同 | 0 | 全为1 |
| x | 不变 | 1 | 全为0 |
比i1高的位：两者完全相同，故不变。
i1位：一个为1，一个为1，故为0。
比i1低的为：一个为1,一个为0，故全为0。
(-x) & \And &x
除最低位的1外，全部置成0。
负数存储的是补码，反码+1.
令第i1位是1，如果有多位是1，i1是最小的。
| 比i1高的位 | i1位 | 比第i1第的位 | |
|---|---|---|---|
| -x的反码 | 和x相反 | 0 | 全为1 |
| -x的补码 | 和x相反 | 1 | 全为0 |
| x的原码 | 不变 | 1 | 全为0 |
比i1高的位： x和-x相反，故全为0。
i1位：x和-x都为1，故结果为1。
比i1低的位： x和-x都为0，故结果为0。
区间(子数组)位与（位或）模板
vector<int> nums;
t r = & x = l r n u m s [ x ] t_r= \Large\And_{x=l}^r nums[x] tr=&x=lrnums[x]
集合s 记录所有的tr，则s的元素数量，最大31个。因为删除重复元素后，tr的二进制1至少少1个。
位或类似，每个不重复的元素至少增加一个1。
最大公约数，也是如此。每次至少除以2。
vector<vector<pair<int, int>>> vNumIndex(nums.size());
for (int i = 0; i < nums.size(); i++) {
if (i) {
for (const auto& [preNum, preIndex] : vNumIndex[i - 1]) {
const int iNew = preNum | nums[i];
if (vNumIndex[i].empty() || (vNumIndex[i].back().first != iNew)) {
vNumIndex[i].emplace_back(make_pair(iNew, preIndex));
}
else {
vNumIndex[i].back().second = preIndex;
}
}
}
if (vNumIndex[i].empty() || (vNumIndex[i].back().first != nums[i])) {
vNumIndex[i].emplace_back(make_pair(nums[i], i));
}
else {
vNumIndex[i].back().second = i;
}
}
vNumIndex[i]记录 nums[x…i]的异或值（不重复）及索引。重复值保留索引大的。x ∈ \in ∈[0,x]。
第二个版本的模版
class CRangCal {
public:
template<class _Pr, class T = int>
static vector<vector<pair<T, int>>> RangCal(const vector<T>& nums, _Pr pr) {
vector<vector<pair<int, int>>> vNumIndex(nums.size());
for (int i = 0; i < nums.size(); i++) {
if (i) {
for (const auto& [preNum, preIndex] : vNumIndex[i - 1]) {
auto iNew = pr(preNum, nums[i]);
if (vNumIndex[i].empty() || (vNumIndex[i].back().first != iNew)) {
vNumIndex[i].emplace_back(make_pair(iNew, preIndex));
}
else {
vNumIndex[i].back().second = preIndex;
}
}
}
if (vNumIndex[i].empty() || (vNumIndex[i].back().first != nums[i])) {
vNumIndex[i].emplace_back(make_pair(nums[i], i));
}
else {
vNumIndex[i].back().second = i;
}
}
return vNumIndex;
}
};
0到x 1的数量
class C1ToXBitCount {
public:
C1ToXBitCount(int iBitCount = 60):m_iBitCount(iBitCount){}
long long TotalBitCount(long long x) {
auto v = BitCount(x);
return std::accumulate(v.begin(), v.end(), 0LL);
}
vector<long long> BitCount(long long x) {
vector<long long> ret(m_iBitCount);
auto cnt = x + 1;
for (int bit = 0; bit < m_iBitCount; bit++) {
long long halfUnit = (1LL << bit);
const auto curBitCount = cnt / 2 / halfUnit * halfUnit + max(0LL, cnt % (2 * halfUnit) - halfUnit);
ret[bit] = curBitCount;
}
return ret;
}
int m_iBitCount = 0;
};
BitCount的返回值v,v[i]表示0到x第i位1的数量。
例题
模板题
【位运算】3097. 或值至少为 K 的最短子数组 II
【动态规划 区间dp 位运算】3117. 划分数组得到最小的值之和
【线段树 区间位运算模板】3117划分数组得到最小的值之和
拆位法
【位运算 拆位法 二分】3007. 价值和小于等于 K 的最大数字
【位运算 拆位法】1835. 所有数对按位与结果的异或和
试填法
【位运算 试填法】【推荐】3022. 给定操作次数内使剩余元素的或值最小
【位运算 反证法 试填法】2897.对数组执行操作使平方和最大
子集状态压缩（枚举子集）
【位运算 子集状态压缩】982按位与为零的三元组
【位运算 状态压缩 枚举子集】1178. 猜字谜
【动态规划】【子集状态压缩】LCP04 覆盖
其它
【位运算】【二分查找】【C++算法】3007价值和小于等于 K 的最大数字
【深度优化(DFS) 记忆化 位运算】：2920收集所有金币可获得的最大积分
【二分查找】【位运算】2354.优质数对的数目
【数论】【分类讨论】【位运算】1611使整数变为 0 的最少操作次数
【动态规划】【位运算】1787. 使所有区间的异或结果为零
【位运算】【脑筋急转弯】2749. 得到整数零需要执行的最少操作数
【数学】【位运算】LeetCoce810. 黑板异或游戏
【位运算】【 数学】【 哈希映射】2857. 统计距离为 k 的点对
【并集查找 图论 位运算】3108. 带权图里旅途的最小代价
【位运算 贪心】2835. 使子序列的和等于目标的最少操作次数
【数学归纳法】【位运算】【异或】3068最大节点价值之和
