状态压缩讲解（炒鸡详细）
2026-04-20 19:36:07
发布于：北京
12阅读
0回复
0点赞
状态压缩详细讲解
状态压缩是用二进制位表示状态，用位运算操作状态的算法技巧，核心是把复杂的集合/状态，压缩成一个整数（二进制），用极快的位运算替代循环/递归处理状态，是竞赛、面试（动态规划、DFS）的高频考点。
一、为什么需要状态压缩？
先看一个经典场景：
有 个物品（），每个物品有选/不选两种状态，要记录哪些物品被选中。
- 普通做法：用数组
bool vis[20]记录，判断、修改都要循环遍历 - 状态压缩：用一个整数表示，比如
5（二进制101）代表第0、2个物品被选
优势：
- 状态存储省空间（一个整数存下所有状态）
- 位运算速度是
- 适配动态规划的状态定义（dp[状态]）
不同情况下状态压缩的时间复杂度都比较大，因此建议数据 时使用（也得分情况考虑）
适用场景：小范围状态枚举（ 用 int， 用long long）。
二、前置知识：必须掌握的位运算
状态压缩的所有操作，都基于这6种核心位运算，熟记符号、含义、用法：
| 运算 | 符号 | 规则 | 状态压缩中的作用 |
|---|---|---|---|
| 按位与 | & | 同为1才为1 | 判断位、保留位 |
| 按位或 | | | 有1就为1 | 设置位、合并状态 |
| 按位异或 | ^ | 相同为0，不同为1 | 翻转位 |
| 左移 | << | 整体左移，右侧补0 | 构造第k位的掩码 |
| 右移 | >> | 整体右移，左侧补0 | 获取第k位的值 |
| 按位取反 | ~ | 0变1，1变0 | 清空指定位 |
构造「掩码」（最基础操作）
掩码：只有第k位是1，其余都是0的二进制数，用于定位操作某一位。
1 << k 等价于 2^k
例：
1 << 0 = 1 (二进制 0001) → 第0位掩码
1 << 2 = 4 (二进制 0100) → 第2位掩码
注意：位运算下标从0开始（和数组一致）。
三、状态压缩的5个核心操作
假设：
state：压缩后的状态整数k：要操作的第k位（从0开始）
1. 判断第k位是否为1
// 公式：(state & (1 << k)) != 0
if (state & (1 << k)) {
// 第k位是1（选中/存在）
} else {
// 第k位是0（未选中/不存在）
}
原理：与掩码做与运算，结果非0 → 该位为1。
2. 将第k位设为1
// 公式：state | (1 << k)
state = state | (1 << k);
// 简写：state |= 1 << k;
原理：或运算有1置1，不影响其他位。
3. 将第k位设为0
// 公式：state & (~(1 << k))
state = state & (~(1 << k));
// 简写：state &= ~(1 << k);
原理：掩码取反后，第k位是0，其余是1，与运算后清空第k位。
4. 翻转第k位（0变1，1变0）
// 公式：state ^ (1 << k)
state ^= 1 << k;
原理：异或运算相同为0，不同为1。
5. 统计状态中1的个数（选中的数量）
// C++ 写法
int cnt = __builtin_popcount(state); // 32位整数
// 如果是long long状态用:__builtin_popcountll(state);
作用：快速知道有多少个物品被选中、多少个城市被访问过。
四、状态枚举：遍历所有可能的状态
当有n个元素时，总状态数 = 2ⁿ（每个元素0/1）。
遍历所有状态的模板：
int n = 3; // 3个元素，状态范围：000 ~ 111（0~7）
for (int state = 0; state < (1 << n); state++) {
// 处理每个状态 state
}
state=0 → 全0（都不选）state=(1<<n)-1 → 全1（都选）
五、实战：3个经典案例（由浅入深）
案例1：子集枚举（打印n个元素的所有子集）
需求：n=3，元素{a,b,c}，用状态压缩打印所有子集。
#include <iostream>
using namespace std;
int main() {
int n = 3;
char ch[] = {'a', 'b', 'c'};
// 遍历所有状态 000~111
for (int state = 0; state < (1 << n); state++) {
cout << "状态" << state << "（二进制";
// 打印二进制（
for (int i = n-1; i >= 0; i--) cout << ((state >> i) & 1);
cout << "）：选中 ";
// 遍历每一位，判断是否选中
for (int k = 0; k < n; k++) {
if (state & (1 << k)) {
cout << ch[k] << " ";
}
}
cout << endl;
}
return 0;
}
输出：
状态0（000）：选中
状态1（001）：选中 a
状态2（010）：选中 b
状态3（011）：选中 a b
状态4（100）：选中 c
状态5（101）：选中 a c
状态6（110）：选中 b c
状态7（111）：选中 a b c
案例2：旅行商问题（TSP，状态压缩DP）
这是状态压缩最经典的应用：
有n个城市，从城市0出发，遍历所有城市恰好一次，求最短路径（n≤20）。
思路
- 状态定义：
dp[state][u]state：压缩的已访问城市集合（二进制第k位=1表示访问过城市k）u：当前所在城市- 含义：访问完
state中的城市，且停在u的最短路径
- 初始状态：
dp[1<<0][0] = 0（只访问城市0，在城市0，距离0） - 转移方程：
从城市u走到未访问的城市v：
dp[state | (1<<v)][v] = min(dp[state | (1<<v)][v], dp[state][u] + cost[u][v]) - 答案：
dp[(1<<n)-1][u]（遍历所有城市，停在任意u的最小值）
核心代码模板
const int INF = 0x3f3f3f3f;
int n;
int cost[20][20]; // 城市间距离
int dp[1<<20][20]; // 状态压缩DP数组
int tsp() {
// 初始化：所有状态设为无穷大
for (int i = 0; i < (1<<n); i++)
for (int j = 0; j < n; j++)
dp[i][j] = INF;
dp[1<<0][0] = 0; // 起点：只访问0号城市
// 遍历所有状态
for (int state = 0; state < (1<<n); state++) {
// 遍历当前所在城市u
for (int u = 0; u < n; u++) {
if (dp[state][u] == INF) continue; // 无效状态跳过
// 遍历要去的城市v
for (int v = 0; v < n; v++) {
// 如果v已经访问过，跳过
if (state & (1 << v)) continue;
// 状态转移：更新新状态
int new_state = state | (1 << v);
dp[new_state][v] = min(dp[new_state][v], dp[state][u] + cost[u][v]);
}
}
}
// 答案：遍历完所有城市（全1状态）的最小距离
return dp[(1<<n)-1][0];
}
案例3：集合判断（A是B的子集？）
- A是B的子集：
(A & B) == A - A和B无交集：
(A & B) == 0
// 示例：A={0,2}（101），B={0,1,2}（111）
int A = 5, B = 7;
if ((A & B) == A) cout << "A是B的子集";
六、状态压缩核心规则与技巧
1. 核心规则
- 下标从0开始：位运算默认第0位对应第一个元素
- 状态范围：
- 数据类型：
- n ≤ 20 →
int（32位足够） - 20 < n ≤ 30 →
long long（64位）
- n ≤ 20 →
- 时间复杂度：O(n·2ⁿ)，n=20时 20*1e6=2e7，完全能跑过
2. 高频技巧
- 去掉最低位的1：
state & (state - 1)
例：6(110) & 5(101) = 4(100) - 获取最低位的1：
state & -state
例：6(110) & -6 = 2(010) - 全1状态：
(1 << n) - 1
七、常见误区
- 下标搞错：把第1位当成第一个元素（必须从0开始）
- 数据溢出：n>20还用int（必须换long long）
- 初始化错误：DP数组没初始化为无穷大，导致结果错误
- 状态遍历顺序错：必须从小到大遍历状态（依赖前序状态）
总结
- 状态压缩 = 二进制表示状态 + 位运算操作状态，专门解决小规模状态枚举问题
- 5个核心操作：判断、置1、置0、翻转、统计1的个数
- 核心应用：子集枚举、状态压缩DP（TSP、棋盘DP）
- 关键：位运算下标从0开始，状态范围0~(1<<n)-1
而且，状态压缩是 GESP 7级 爱考的知识点！
有帮助，赞一个