C++位运算、状态压缩、枚举子集汇总_位运算枚举子集

本文涉及知识点

证明容斥原理和证明集合枚举都用到了：二项式定理
【数学归纳法 组合数学】容斥原理

基础知识

位运算优先级

位运算的结合性都是从左到右。优先级低的先运算。

注意：不同的编译系统的实现可能不同,所以加上括号保险。就算你把运算顺序牢记于心，你的同事未必记得。

异或（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$\cdots a_{2n-2},a_{2n-1}$ }
思路：根据性质三，答案就是这2n-1的数的异或积。

位与(&)

定义： x1 $\&$ x2 = y。对二进制位分别运算，x1和x2的某二进制位全部为1，y对应的二进制位为1；否则为0。
性质一：
n个数依次位与结果为y，如果这n个数的某二进制位全部为1,则y的对应二进制位为1，否则为0。
推论一：
根据性质一，可得如下推论：n个数求与积，可以任意调换数的顺序结果不变。
性质二：
(-1)&x = x
性质三：
x1 $\&$ x2 = y <=min(x1,x2)

位或（|）

定义： x1 $\vee$ x2 = y。对二进制位分别运算，x1和x2的某二进制位全部为0，y对应的二进制位为0；否则为1。
性质一：
n个数依次位与结果为y，如果这n个数的某二进制位全部为0,则y的对应二进制位为0，否则为1。
推论一：
根据性质一，可得如下推论：n个数求与积，可以任意调换数的顺序结果不变。
性质二：
0 $\vee$ x = x
性质三：
x1 $\vee$ x2 >= max(x1,x2)

取反（~）

定义：各二进制位0变1,1变0。

位左移（<<)、位右移(>>)

x << n ，相当于x $\times$ 2ⁿ
x >> n， 相当于 x $÷$ 2ⁿ

状态压缩

用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(3ⁿ)。下面利用二项式定理。
0被maxMask 所有子集枚举，共2ⁿ次。
有且仅有一个二进位为1的数共有$\left(\genfrac{}{}{0ex}{}{n}{1}\right)$个，被2^n-1个子集枚举。除当前位必须是1，其它位01皆可。
有且仅有2个二进位为1的数共有$\left(\genfrac{}{}{0ex}{}{n}{2}\right)$个，被2^n-2个子集枚举。
$$\begin{gathered} \sum _{i:0}^n\left(\genfrac{}{}{0ex}{}{n}{i}\right)1^i{2}^{n-i} \\ =(1+2{)}^n=3^n根据二项式定理 \end{gathered}$$

常见的运算

x是正整数
(x-1)$\&$ x :将最低位的1设置成0。
令第i1位是1，如果有多位是1，i1是最小的。

比i1高的位：两者完全相同，故不变。
i1位：一个为1，一个为1，故为0。
比i1低的为：一个为1,一个为0，故全为0。

(-x)$\&$x
除最低位的1外，全部置成0。
负数存储的是补码，反码+1.
令第i1位是1，如果有多位是1，i1是最小的。

比i1高的位： x和-x相反，故全为0。
i1位：x和-x都为1，故结果为1。
比i1低的位： x和-x都为0，故结果为0。

区间(子数组)位与（位或）模板

vector<int> nums;
1

$$t_r={\&}_{x=l}^{r}nums[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;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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最大节点价值之和

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。