二进制法
给定一个集合，枚举所有可能的子集。枚举子集的方法有很多，本节我们介绍一种代码编写非常方便的枚举子集方法——二进制法
我们可以用二进制的一位表示集合对应某一元素的选取状态， <math> <semantics> <mrow> <mn> 1 </mn> </mrow> <annotation encoding="application/x-tex"> 1 </annotation> </semantics> </math>1 表示选取， <math> <semantics> <mrow> <mn> 0 </mn> </mrow> <annotation encoding="application/x-tex"> 0 </annotation> </semantics> </math>0 表示未选取。
举个例子，我们拥有一个集合 { <math> <semantics> <mrow> <mn> 0 </mn> <mo separator="true"> , </mo> <mn> 1 </mn> <mo separator="true"> , </mo> <mn> 2 </mn> <mo separator="true"> , </mo> <mn> 3 </mn> <mo separator="true"> , </mo> <mn> 4 </mn> <mo separator="true"> , </mo> <mn> 5 </mn> <mo separator="true"> , </mo> <mn> 6 </mn> </mrow> <annotation encoding="application/x-tex"> {0,1,2,3,4,5,6} </annotation> </semantics> </math>0,1,2,3,4,5,6}。
那么二进制0101101就代表子集合 { <math> <semantics> <mrow> <mn> 0 </mn> <mo separator="true"> , </mo> <mn> 2 </mn> <mo separator="true"> , </mo> <mn> 3 </mn> <mo separator="true"> , </mo> <mn> 5 </mn> </mrow> <annotation encoding="application/x-tex"> {0,2,3,5} </annotation> </semantics> </math>0,2,3,5}，如下图所示。
| 2进制数位 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
|---|---|---|---|---|---|---|---|
| 二进制制数值 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 选取的元素 | - | 5 | - | 3 | 2 | - | 0 |
位运算
代码中对于二进制的处理可以用位运算来实现。位运算是对二进制的每一位进行计算，所以每一位只有 <math> <semantics> <mrow> <mn> 0 </mn> </mrow> <annotation encoding="application/x-tex"> 0 </annotation> </semantics> </math>0 或 <math> <semantics> <mrow> <mn> 1 </mn> </mrow> <annotation encoding="application/x-tex"> 1 </annotation> </semantics> </math>1 两种可能。先介绍三种常用的位运算符：与 &、或|、亦或^，运算规则如下表所示
| A | B | A&B | A|B | A^B |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 |
- 与运算：两者都为 <math> <semantics> <mrow> <mn> 1 </mn> </mrow> <annotation encoding="application/x-tex"> 1 </annotation> </semantics> </math>1 时，结果为 <math> <semantics> <mrow> <mn> 1 </mn> </mrow> <annotation encoding="application/x-tex"> 1 </annotation> </semantics> </math>1 ，否则为 <math> <semantics> <mrow> <mn> 0 </mn> </mrow> <annotation encoding="application/x-tex"> 0 </annotation> </semantics> </math>0
- 或运算：两者都为 <math> <semantics> <mrow> <mn> 0 </mn> </mrow> <annotation encoding="application/x-tex"> 0 </annotation> </semantics> </math>0 时，结果为 <math> <semantics> <mrow> <mn> 0 </mn> </mrow> <annotation encoding="application/x-tex"> 0 </annotation> </semantics> </math>0 ，否则为 <math> <semantics> <mrow> <mn> 1 </mn> </mrow> <annotation encoding="application/x-tex"> 1 </annotation> </semantics> </math>1
- 异或运算：两者同为 <math> <semantics> <mrow> <mn> 0 </mn> </mrow> <annotation encoding="application/x-tex"> 0 </annotation> </semantics> </math>0 或者 <math> <semantics> <mrow> <mn> 1 </mn> </mrow> <annotation encoding="application/x-tex"> 1 </annotation> </semantics> </math>1 时，结果为 <math> <semantics> <mrow> <mn> 1 </mn> </mrow> <annotation encoding="application/x-tex"> 1 </annotation> </semantics> </math>1，否则为 <math> <semantics> <mrow> <mn> 0 </mn> </mrow> <annotation encoding="application/x-tex"> 0 </annotation> </semantics> </math>0
两个十进制整数进行位运算结果是多少呢？举个例子 A = 25 与 B = 14 做位运算，A 转化为二进制是 11001，B 转化为二进制是 01110，那么结果如下图
| A = 25 | 1 | 1 | 0 | 0 | 1 |
|---|---|---|---|---|---|
| B = 14 | 0 | 1 | 1 | 1 | 0 |
| A&B = 8 | 0 | 1 | 0 | 0 | 0 |
| A|B = 31 | 1 | 1 | 1 | 1 | 1 |
| A^B = 23 | 1 | 0 | 1 | 1 | 1 |
注意： 不要把 A^B 当成 <math> <semantics> <mrow> <msup> <mi> A </mi> <mi> B </mi> </msup> </mrow> <annotation encoding="application/x-tex"> A^B </annotation> </semantics> </math>AB
位运算符
位运算符中有两种操作，左移<<和右移>>。右移具体还分为带符号右移与无符号右移，本节我们提到的右移指的是带符号右移，无符号右移使用较少，在这里不做解释。
对于A << B,表示把 A 转化为二进制后向左移动 B 位（在末尾添加 B 个 0 )。
对于A >> B,表示把 A 转化为二进制后向右移动 B 位（删除末尾的 B 位）。
比如2 << 2, 2 转化为二进制则是 10,那么就是 10 左移动 2 位，就变成了二进制1000,转化为十进制是 8,所以 2 << 2 = 8 。
举个例子
我们来看一个可以用二进制枚举的方法解决的题目。
话说大诗人李白，一生好饮。幸好他从不开车。
—天，他提着酒壶，从家里出来，酒壶中有酒两斗。他边走边唱:
- 无事街上走，提壶去打酒。
- 逢店加一倍，遇花喝一斗。
这一路上，他一共遇到店 5 次，遇到花 10 次，已知最后一次遇到的是花，他正好把酒喝光了。请你计算李白遇到店和花的次序，有多少种可能的方案。
解答
这个题目解法很多，二进制枚举是一种写起来非常简洁的解法。我们已知遇店 5 次，遇花 10 次，并且最后一次遇到花，正好把酒喝光。那么我们可以把店作为二进制中的 1，把花作为二进制中的 0，因为已经确定最后一次遇到的是花，所以我们需要判断枚举的结果是否刚好有 5 个 1 和 9 个 0。那么我们就枚举出 14 位二进制的所有可能并加以判断即可，判断思路为判断二进制是否有 9 个 0，5 个 1,并且最终酒刚好剩 1 斗。
根据这个思路，可以写出如下的代码：
int ans = 0;
for (int i = 0; i < (1<<14); ++i) {
int tot_1 = 0;
int tot_0 = 0;
int num = 2;
for (int j = 0; j < 14; ++j) {
if (i&(1 << j)) { // 这里判断二进制 i 从右数第 j + 1 位是否为 1
tot_1++;
num = num * 2;
} else {
tot_0++;
num = num - 1;
}
}
if (tot_1 == 5 && tot_0 == 9 && num == 1) {
++ans; // 记录合法方案数
}
}
自己补充
二进制法适用范围：
- 一定的范围，int 的范围是 2 <math> <semantics> <mrow> <msup> <mn> 32 </mn> </msup> </mrow> <annotation encoding="application/x-tex"> ^{32} </annotation> </semantics> </math>32 - 1，再大遍历耗时太久，也就没意义了
- 两种对应状态，比如店与花、选取与不选取、买与不买、召唤与不召唤
二进制法通解过程：
- 确定状态，0 1 分别表示什么状态
- 确定枚举范围，即外部循环是什么
- 确定目标所求，即一次外部循环哪些需要求
- 确定子集范围，即内部循环是什么
- 确定具体所求，即一次内部循环哪些量需要改变
- 确定解，即什么样的遍历效果是我们所求，需要哪些限定条件
二进制法通解：
// 枚举范围
for(int i=0;i<(1 << n);i++){
// 列出变化变量
int ...;
// 遍历每一位
for(int j=0;j<n;j++){
if(i & (1 << j)){
// 如果满足状态，遍历随着变化
}
}
//当遍历完一种情况，累积量
if(...)
...;
}
京公网安备 11010502036488号