【算法学习笔记】二进制枚举——用二进制表示状态

前言

之前做枚举题的时候，通常都是通过循环把所有可能的情况试一遍。但如果每个元素都有选和不选两种状态，随着元素数量增加，需要枚举的情况也会越来越多。

这时候就可以用到二进制枚举。

二进制枚举的核心思路并不复杂，就是利用二进制中的 0 和 1 表示不同状态，再通过位运算枚举所有可能的情况。

这篇文章主要整理二进制枚举的基本用法，以及三个相关例题：子集、费解的开关和 Even Parity。

一、二进制枚举的基本思想

假设有一个数组：

nums = {1, 2, 3};

现在要求枚举数组中所有可能的子集。

对于每个元素来说，只有两种选择：

• 选择这个元素，用 1 表示。
• 不选择这个元素，用 0 表示。

因此，可以用一个二进制数来表示当前的选择情况。

这里规定二进制数的最低位对应数组的第一个元素，也就是 nums[0]。

那么所有情况如下：

三个元素，每个元素都有两种状态，所以总共有：2^3=8 种情况。

如果数组有 n 个元素，那么总共有 (2^n) 种状态。

所以直接枚举：

for(int st = 0; st < (1 << n); st++)
{
// st 代表当前枚举到的状态
}

其中 1 << n 就是 (2^n)。

这样就可以把所有可能的状态全部枚举出来。

二、二进制枚举常用的位运算

使用二进制枚举，离不开位运算。这里主要记录几个经常用到的操作。

1. 左移运算 <<

左移运算可以快速计算 2 的整数次幂。

例如：

1 << 3

二进制变化：

0001 << 3 = 1000

转换成十进制就是 8。

因此：1 << n = 2^n

在枚举所有状态时，经常会看到：

for(int st = 0; st < (1 << n); st++)

2. 右移运算 >> 和按位与 &

这两个运算经常配合使用，用来判断二进制某一位的状态。

常见写法：

(st >> i) & 1

它的作用是取出 st 的第 i 位。

例如：

int st = 5; // 二进制：101

cout << ((st >> 0) & 1) << endl; // 1
cout << ((st >> 1) & 1) << endl; // 0
cout << ((st >> 2) & 1) << endl; // 1

先右移 i 位，让目标位置来到最低位，再和 1 进行按位与操作，就能得到这一位的值。

如果结果为 1，说明对应位置被选中；如果结果为 0，说明没有被选中。

3. 异或运算 ^

异或运算在二进制枚举相关题目中也很常见。

它有一个很重要的特点：

可以看到，相同为 0，不同为 1。

所以异或经常用来实现状态翻转：

x ^= 1;

如果原来是 0，就变成 1；如果原来是 1，就变成 0。

另外，异或还满足交换律和结合律。

三、例题一：子集

题目：子集

给定一个没有重复元素的整数数组 nums，要求返回数组所有可能的子集。

例如：

nums = [1, 2, 3]

输出：

[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

思路分析

这道题刚好可以使用前面介绍的二进制枚举。

数组中有 n 个元素，每个元素只有选和不选两种情况，因此总共有 (2^n) 种可能。

我们可以让 st 从 0 开始，一直枚举到 (2^n-1)。

每次枚举一个状态，就检查它的每个二进制位：

• 如果第 i 位为 1，就把 nums[i] 放入当前子集。
• 如果第 i 位为 0，就跳过这个元素。

这样每个状态都能对应一个子集，最终就能得到所有可能的结果。

代码实现

class Solution
{
public:
vector<vector<int>> subsets(vector<int>& nums)
{
vector<vector<int>> ret;
int n = nums.size();

// 枚举所有的状态
for(int st = 0; st < (1 << n); st++)
{
// 根据 st 的状态，还原出要选的数
vector<int> tmp; // 从当前选的子集
for(int i = 0; i < n; i++)
{
if((st >> i) & 1) tmp.push_back(nums[i]);
}
ret.push_back(tmp);
}

return ret;
}
};

复杂度分析

一共有 (2^n) 种状态，每种状态都需要遍历 n 个元素。

• 时间复杂度：(O(n * 2^n))
• 额外空间复杂度：(O(n))，不考虑返回结果所占用的空间。

这道题算是二进制枚举最基础的应用。只要理解了如何用二进制表示选择状态，代码其实很好写。

四、例题二：费解的开关

题目：费解的开关

有 25 盏灯，排列成一个 5×5 的矩阵，每盏灯只有开和关两种状态。

每次按下一个开关，会改变当前位置以及上下左右相邻位置的灯的状态。

给定初始状态，要求判断能否在 6 步以内让所有灯都亮起来，如果可以，输出最少按动次数，否则输出 -1。

1. 分析题目性质

如果直接枚举 25 个开关的所有按法，那么总共有：2^{25} 种情况。

显然，这样枚举的范围比较大。

仔细观察题目，可以发现几个性质：

第三点是这道题的关键。

为什么第一行确定之后，后面的行也就确定了？

假设第一行某个位置的灯没有亮，那么想要改变这个位置的状态，只能按它正下方的开关。

因为第二行的开关只能影响第一行中对应位置，第一行其他位置的开关已经无法再影响它了。

所以，只要确定第一行的按法，就可以从上到下依次推出后面每一行的按法。

原本需要枚举 (2^{25}) 种情况，现在只需要枚举第一行的：2^5=32 种情况。

2. 使用二进制存储每一行

每行有 5 个位置，可以直接使用一个整数的低 5 位来表示这一行的状态。

例如：

10101

就可以表示这一行的灯的状态。

这里还有一个小技巧：读取数据时，可以把原来的 0 和 1 反过来存储。

也就是：

• 原来的 0 存成 1。
• 原来的 1 存成 0。

这样，题目要求所有灯都亮，就变成了所有位置都为 0。

最后只需要判断最后一行是否为 0 即可。

3. 枚举第一行的按法

第一行有 5 个开关，因此直接枚举：

for(int st = 0; st < (1 << 5); st++)
{
// st 表示第一行的一种按法
}

如果 st 的第 i 位为 1，就说明第一行第 i 个开关需要按下。

另外，还需要统计当前按法一共按了多少次开关。

可以使用下面这个函数统计二进制中 1 的个数：

int calc(int x)
{
int cnt = 0;

while(x)
{
cnt++;
x &= x – 1;
}

return cnt;
}

这里的：

x &= x – 1;

每执行一次，就会消掉 x 二进制中最低位的一个 1。

所以循环执行的次数，就是二进制中 1 的个数。

4. 如何推出下一行的按法？

这部分是整道题最重要的地方。

假设当前行的按法已经确定，记作 push。

按下开关后，会影响当前行和下一行：

• 当前行对应位置的灯会改变。
• 当前行左右相邻位置的灯会改变。
• 下一行对应位置的灯会改变。

由于按下开关就是把 0 变成 1，或者把 1 变成 0，所以可以使用异或运算来实现状态翻转。

当前行更新：

t[i] = t[i] ^ push ^ (push << 1) ^ (push >> 1);

其中：

• push：改变当前位置。
• push << 1：改变一个相邻位置。
• push >> 1：改变另一个相邻位置。

不过，左移可能会产生超出 5 位范围的高位，因此需要进行位截断：

t[i] &= (1 << 5) – 1;

下一行只会受到当前行对应位置的影响：

t[i + 1] ^= push;

那么下一行应该怎么按？

其实也很简单。

当前行按完之后，哪些位置还没有达到目标状态，下一行就按下这些位置对应的开关。

所以：

push = t[i];

这样就能得到下一行的按法。

不断重复这个过程，直到最后一行。

如果最后一行的状态为 0，就说明所有灯都已经亮了。此时统计按动次数，并更新最小值。

最后判断最小次数是否超过 6：

• 不超过 6，输出最小次数。
• 超过 6，输出 -1。

5.代码实现

#include <iostream>
#include <cstring>

using namespace std;

const int N = 10;

int n = 5;
int a[N]; // 用二进制表示，来存储灯的状态
int t[N]; // 备份 a 数组

// 计算 x 的二进制表示中一共有多少个 1
int calc(int x)
{
int cnt = 0;
while(x)
{
cnt++;
x &= x – 1;
}
return cnt;
}

int main()
{
int T; cin >> T;

while(T—)
{
// 多组测试时，一定要注意清空之前的数据
memset(a, 0, sizeof a);

for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
char ch; cin >> ch;
// 存成相反的
if(ch == '0') a[i] |= 1 << j;
}
}

int ret = 0x3f3f3f3f; // 统计所有合法的按法中的最小值
// 枚举第一行所有的按法
for(int st = 0; st < (1 << n); st++)
{
memcpy(t, a, sizeof a);
int push = st; // 当前行的按法
int cnt = 0; // 统计当前按法下一共按了多少次

// 依次计算后续行的结果以及按法
for(int i = 0; i < n; i++)
{
cnt += calc(push);
// 修改当前行被按的结果
t[i] = t[i] ^ push ^ (push << 1) ^ (push >> 1);
t[i] &= (1 << n) – 1; // 清空影响
// 修改下一行的状态
t[i + 1] ^= push;
// 下一行的按法
push = t[i];
}

if(t[n – 1] == 0) ret = min(ret, cnt);
}

if(ret > 6) cout << –1 << endl;
else cout << ret << endl;
}

return 0;
}

6. 这道题的核心

这道题比较值得学习的地方，不只是使用二进制枚举第一行，而是通过观察题目性质，把原本需要枚举整个矩阵的过程，变成了只枚举第一行。

后面的状态不需要继续枚举，而是根据前面的状态直接推导出来。

做这类题时，不能只想着暴力枚举所有情况，有时候找到状态之间的联系，才能真正减少枚举量。

五、例题三：Even Parity

题目：Even Parity

给定一个 n×n 的 01 矩阵，要求尽可能少地把 0 变成 1，使矩阵变成偶数矩阵。

所谓偶数矩阵，就是每个位置上下左右相邻元素（如果存在）的和都必须是偶数。

如果不存在合法方案，输出 -1。

1. 分析题目性质

这道题和上一道费解的开关有些相似。

首先可以发现：

所以我们依然不需要枚举整个矩阵的状态，只需要枚举第一行的最终状态，然后根据规则推出后面的行。

2. 枚举第一行的最终状态

第一行有 n 个位置，每个位置都有 0 和 1 两种状态。

因此直接枚举：

for(int st = 0; st < (1 << n); st++)

每个 st 就代表第一行的一种最终状态。

不过需要注意，题目只允许 0 变成 1，因此还需要判断当前枚举的状态是否合法。

比较原始状态 x 和最终状态 y：

• 0 变成 1：合法，改变次数加一。
• 1 变成 0：不合法，直接跳过当前状态。
• 0 变成 0：不需要改变。
• 1 变成 1：不需要改变。

可以通过逐位比较来完成这个判断。

int calc(int x, int y)
{
int sum = 0;

for(int i = 0; i < n; i++)
{
// 0 -> 1，改变次数加一
if(((x >> i) & 1) == 0 &&
((y >> i) & 1) == 1)
{
sum++;
}

// 1 -> 0，不合法
if(((x >> i) & 1) == 1 &&
((y >> i) & 1) == 0)
{
return –1;
}
}

return sum;
}

3. 根据当前行推出下一行

这是本题另一个关键点。

因为题目要求每个位置上下左右相邻元素的和都是偶数，所以可以利用异或运算的性质来推导下一行。

当一个位置上下左右相邻元素中 1 的数量是偶数时，这几个位置异或起来的结果就是 0。

因此，当上一行和当前行的最终状态确定之后，下一行的状态也就确定了。

推导公式：

a[i + 1] = (a[i] >> 1)
^ (a[i] << 1)
^ a[i – 1];

这里：

• a[i] >> 1：当前行右移一位。
• a[i] << 1：当前行左移一位。
• a[i – 1]：上一行对应位置的状态。

最后同样需要进行位截断：

a[i + 1] &= (1 << n) – 1;

这是为了保证结果只保留 n 位，避免多余的高位影响后续判断。

4. 统计最小改变次数

每次枚举第一行的最终状态后，都需要依次推出后面的行。

在推导过程中：

如果整个过程都合法，那么当前方案就是一个可行方案。

最后在所有可行方案中取改变次数最少的结果。

如果没有任何合法方案，就输出 -1。

5.代码实现

#include <iostream>
#include <cstring>

using namespace std;

const int N = 20;

int n;
int a[N]; // 用二进制存储状态
int t[N]; // 备份

// 判断 x->y 是否合法
// 返回 -1，表示不合法
// 其余的数，表示合法，并且表示 0->1 的次数
int calc(int x, int y)
{
int sum = 0;

for(int i = 0; i < n; i++)
{
if(((x >> i) & 1) == 0 && ((y >> i) & 1) == 1) sum++;
if(((x >> i) & 1) == 1 && ((y >> i) & 1) == 0) return –1;
}

return sum;
}

int solve()
{
int ret = 0x3f3f3f3f; // 记录最小的改变次数

// 枚举第一行的最终状态
for(int st = 0; st < (1 << n); st++)
{
memcpy(t, a, sizeof a);

int change = st;
int cnt = 0; // 统计 0->1 的次数
bool flag = 1;

for(int i = 1; i <= n; i++)
{
// 先判断 change 是否合法
int c = calc(t[i], change);
if(c == –1)
{
flag = 0;
break;
}

cnt += c; // 累加次数
// 当前行的最终状态
t[i] = change;
// 计算下一行的最终状态
change = t[i – 1] ^ (t[i] << 1) ^ (t[i] >> 1);
change &= (1 << n) – 1;
}
if(flag) ret = min(ret, cnt);
}

if(ret == 0x3f3f3f3f) return –1;
else return ret;
}

int main()
{
int T; cin >> T;

for(int k = 1; k <= T; k++)
{
// 多组测试数据，记得清空
memset(a, 0, sizeof a);

cin >> n;
for(int i = 1; i <= n; i++) // 避免越界访问
{
for(int j = 0; j < n; j++)
{
int x; cin >> x;
if(x) a[i] |= 1 << j;
}
}

printf("Case %d: %d\\n", k, solve());
}

return 0;
}

这道题和费解的开关的整体思路其实很像：先枚举第一行，再利用已经确定的状态推导后面的行。

只不过两道题的状态转移规则不同，具体实现也有所区别。

六、总结

二进制枚举本质上还是暴力枚举，只不过利用二进制来表示每个元素的状态，再通过位运算完成状态的判断和修改。

这一部分主要需要掌握以下几点：

1. 状态表示

使用二进制中的 0 和 1 表示每个元素的两种状态。

2. 枚举所有状态

通过：

for(int st = 0; st < (1 << n); st++)

就能枚举 n 个元素的所有可能状态。

3. 判断某一位的状态

通过：

(st >> i) & 1

可以快速取出第 i 位的值。

4. 利用题目性质优化枚举

费解的开关和 Even Parity 这两道题都没有直接枚举整个矩阵，而是通过第一行的状态推导后面的状态，大幅减少了枚举范围。

最后还需要注意一点：二进制枚举虽然方便，但它的时间复杂度仍然可能是指数级的。n 稍微增大，(2^n) 就会增长得很快，所以做题时一定要结合数据范围判断是否适合使用。