1. 从“开关灯”到“状态压缩”一个直观的引入如果你写过一些算法题尤其是涉及“全排列”、“子集”或者“旅行商问题TSP”这类题目大概率会碰到一种让人又爱又恨的解法——状态压缩动态规划。第一次看到用整数来表示一个集合用位运算来操作状态转移时那种感觉就像在看天书。但一旦你理解了它背后的思想就会发现它其实是一种极其优雅且高效的抽象工具。今天我们不谈复杂的动态规划状态转移方程就聊聊这个工具最基础的部分二进制状态压缩和位运算。简单来说二进制状态压缩的核心思想就是用一串二进制位通常用一个整数来存储来表示一组事物的“是/否”、“开/关”、“选中/未选中”等二元状态。想象一下你有8个房间的灯你想记录哪些灯是开着的。笨办法是用一个长度为8的布尔数组lights[8]。而状态压缩告诉你用一个8位的二进制数就够了。比如01001101这个二进制数从右往左或从左往右取决于约定每一位代表一个房间1表示开灯0表示关灯。这个二进制数转换成十进制就是77。于是一个整数77就完整地编码了8个灯的状态。那么如何高效地操作这个整数即这个压缩后的状态呢答案就是位运算。位运算直接对整数的二进制位进行操作速度极快是状态压缩得以实现高效查询和更新的基石。理解位运算不仅是学习状态压缩的“前置知识”更是深入理解计算机底层数据表示和操作的必修课。很多人在学习时只记住了与、|或这些符号但一到实际应用比如判断某个灯是否开着或者打开某个灯的同时关闭另一个灯就不知道如何组合这些操作了。这篇文章我们就从最底层的位运算操作讲起掰开揉碎让你不仅知道怎么用更明白为什么要这么用以及在实际编码中那些容易踩的坑。2. 位运算的六把“手术刀”基础操作全解析位运算操作的是整数的二进制形式。在大多数编程语言中我们讨论的是有符号整数如int的补码表示。但为了简化理解状态压缩我们通常先将其视为无符号的非负整数来操作其位模式。下面这六种操作是核心中的核心。2.1 按位与精准的“掩码”提取器运算规则两位都为1时结果才为1。1 1 1 1 0 0 0 1 0 0 0 0核心用途检查特定位是否为1判断状态或者清除置0某些位。检查第k位从0开始计数是否为1这是最常用的操作。我们创建一个只有第k位是1其余位都是0的数这个数称为“掩码”Mask即mask 1 k。然后用原数state与mask进行按位与操作。公式(state (1 k)) ! 0原理如果state的第k位是1那么1k的第k位也是1与操作后结果非零具体值就是1k。如果第k位是0那么与操作后所有位都是0结果为0。示例判断状态state 13(二进制1101) 的第2位从右数第3位是否为1。k 2,mask 1 2 4(二进制0100)。state mask 1101 0100 0100(十进制4)。结果4 ! 0所以第2位是1。清除最低位的1这是一个经典技巧公式为state (state - 1)。原理state - 1会把state二进制表示中最低位的1变成0并且这个最低位1之后的所有0都变成1。两者相与恰好把原数最低位的1及其后面的位全部清零。示例state 12(二进制1100)。state - 1 11(二进制1011)。1100 1011 1000(二进制8)。成功清除了最低位的那个1。应用快速计算一个二进制数中有多少个1Brian Kernighan算法或者判断一个数是否是2的幂2的幂的二进制只有一个1所以n (n-1) 0。取特定位区间的值结合移位操作可以提取连续几位。例如想取state的第3到第5位共3位。先右移3位去掉低3位state 3。再与一个低3位全为1的掩码相与(state 3) ((1 3) - 1)。(13)-1得到111二进制即7。2.2 按位或|强力的“开关”设置器运算规则两位中有一个为1时结果就为1。1 | 1 1 1 | 0 1 0 | 1 1 0 | 0 0核心用途将特定位设置为1打开某个状态。将第k位设置为1同样使用掩码mask 1 k。公式state state | (1 k)或简写为state | (1 k)。原理无论state第k位原来是0还是1与一个第k位为1的数进行或操作结果第k位一定是1。示例将状态state 9(二进制1001) 的第1位设为1。mask 1 1 2(二进制0010)。state | mask 1001 | 0010 1011(十进制11)。2.3 按位异或^巧妙的“翻转”与“切换器”运算规则两位不同时结果为1相同时结果为0。1 ^ 1 0 1 ^ 0 1 0 ^ 1 1 0 ^ 0 0核心用途翻转特定位1变00变1以及不使用临时变量交换两个数。翻转第k位使用掩码mask 1 k。公式state state ^ (1 k)或state ^ (1 k)。原理与1异或位翻转1^10 0^11与0异或位不变。mask在第k位是1其他位是0因此只翻转第k位。示例翻转state 11(1011) 的第2位。mask 1 2 4(0100)。state ^ mask 1011 ^ 0100 1111(十进制15)。第2位从0变成了1。交换两个数a a ^ b; b a ^ b; a a ^ b;。这是一个经典的技巧利用了异或的自反性a ^ a 0和结合律。但在实际工程中可读性较差现代编译器对使用临时变量的交换优化得很好所以这个技巧更多见于面试题。重要性质自反性a ^ a 0。与0异或不变a ^ 0 a。结合律/交换律。由以上可得a ^ b ^ a b。这个性质在一些找“只出现一次的数字”算法题中非常有用。2.4 按位取反~全局的“位翻转”运算规则将每一位取反1变00变1。~1 0 ~0 1核心用途通常用于配合其他操作生成掩码或者整体翻转一个位集合在状态压缩中需谨慎使用。这里有一个巨大的坑关乎你搜索热词里提到的“反码运算”和“进位”问题。在大多数编程语言中~操作符是对整数的所有位包括符号位进行取反。对于一个32位的int类型数n~n的结果是-n-1。这是因为计算机使用补码存储整数取反操作是补码意义上的按位取反而不是简单的二进制位翻转。示例与坑点假设我们用一个8位模型简化state 5(二进制00000101)。如果你天真地以为~5是11111010十进制250那就错了。在补码体系中~5计算的是5的补码按位取反。5的补码是00000101取反后是11111010而这个二进制数作为有符号整数的补码它表示的是-6。因为-6的补码正是11111010计算过程6的原码00000110- 反码11111001- 补码11111010。所以~5的结果是-6。公式~n -n - 1成立。在状态压缩中如何正确使用~状态压缩时我们通常只关心低n位。直接使用~state会翻转所有32位得到负数这通常不是我们想要的。我们只想翻转低n位。正确做法先构造一个低n位全为1高位全为0的掩码full_mask (1 n) - 1。然后我们想得到state低n位的按位取反结果。公式(~state) full_mask。原理~state翻转了所有位包括高位无用的部分然后 full_mask将高位全部清零只保留低n位这低n位正是我们想要的state低n位的翻转结果。示例state 5(00000101)我们只关心低4位 (n4)。full_mask (14)-1 15(00001111)。~5得到11111010(这是-6的补码表示)。(~5) 15 11111010 00001111 00001010(十进制10)。而5的低4位是0101翻转后确实是1010(十进制10)。注意这就是你搜索热词中“反码运算时产生的进位需要循环进位”在高级语言中的体现。在硬件或纯二进制运算中按位取反就是简单的翻转。但在高级语言操作有符号整数时~运算符的结果被解释为一个新的有符号整数补码这个解释过程就隐含了“符号”和“数值范围”的概念并非简单的位翻转。我们通过 full_mask来屏蔽高位本质上就是抛弃了因符号位变化而产生的“进位”影响将运算限定在我们关心的位范围内。2.5 左移与右移位的“搬运工”左移a b将a的二进制位全部向左移动b位低位补0高位溢出丢弃。效果相当于乘以2^b在不溢出的情况下。核心用途快速生成掩码如1 k生成第k位为1的掩码。(1 n) - 1生成低n位全1的掩码。右移a b将a的二进制位全部向右移动b位。这里有个关键区别对于有符号整数如int右移操作是算术右移高位补的是符号位即正数补0负数补1。对于无符号整数如unsigned int右移操作是逻辑右移高位补0。在状态压缩中的建议为了可移植性和避免负数带来的意外强烈建议使用无符号整数如unsigned int,uint32_t来进行状态压缩。这样就是逻辑右移行为符合直觉。用途配合操作提取特定位或者快速除以2^b对于非负整数。3. 状态压缩的实战编码技巧与“骚操作”理解了基本操作我们来看看如何将它们组合起来解决状态压缩中的常见任务。假设我们用int或unsigned int的二进制低n位来表示n个元素的状态集合n最好小于等于32对于64位系统可以用long long。3.1 基础操作封装通常我们会定义一些宏或内联函数让代码更清晰// 假设状态 state 是 unsigned int 类型 #define GET_BIT(state, k) (((state) (k)) 1) // 获取第k位返回0或1 #define SET_BIT(state, k) ((state) | (1U (k))) // 将第k位设为1 #define CLR_BIT(state, k) ((state) ~(1U (k))) // 将第k位设为0 #define FLIP_BIT(state, k) ((state) ^ (1U (k))) // 翻转第k位 #define LOWBIT(x) ((x) -(x)) // 获取最低位的1所对应的幂值另一个重要技巧注意1U表示无符号整数1避免左移符号位的问题。3.2 枚举所有子集一个经典模式给定一个表示集合的二进制数state如何枚举它的所有子集这里的“子集”指的是二进制表示中某些位为1的集合的所有可能组合即某些位可以变成0但原本是0的位不能变成1。算法sub state; sub (sub - 1) state;循环直到sub 0。原理sub - 1会将sub最低位的1变成0后面所有位变成1。再与原来的state相与保证了结果仍然是state的子集不会出现state中为0的位变成1。这个循环会以“递减”的顺序枚举出所有子集按二进制数值。示例state 6(二进制110表示第1和第2位元素存在)。初始sub 110(6) - 子集 {元素1 元素2}sub (110 - 1) 110 101 110 100(4) - 子集 {元素2}sub (100 - 1) 110 011 110 010(2) - 子集 {元素1}sub (010 - 1) 110 001 110 000(0) - 空集 {}循环结束。枚举了所有4个子集。这个技巧在状态压缩DP中遍历状态的前置子集时非常高效。3.3 判断状态合法性掩码的进阶应用有时状态需要满足一些约束比如不能有两个相邻的位同时为1在棋盘放置问题中很常见。我们如何快速判断一个状态s是否合法判断是否有相邻的1(s (s 1)) 0。原理将s右移一位再与自身相与如果结果非零说明存在某一位和它的前一位同时为1。判断是否有间隔一位的1(s (s 2)) 0。更复杂的约束可以预处理所有合法的单行状态。对于n个位置总状态数2^n通常不大可以提前枚举并过滤掉非法状态存到一个数组valid_states中。在DP时直接遍历这个合法状态数组效率更高。3.4 状态转移中的位运算以TSP为例在旅行商问题TSP的状态压缩DP中状态dp[state][i]表示已经访问过的城市集合为state当前位于城市i的最小花费。其中state的第i位为1表示城市i已访问。 状态转移dp[state][i] min(dp[state][i], dp[prev_state][j] dist[j][i])。 其中prev_state是state去掉城市i后的状态即prev_state state ^ (1 i)。 并且需要满足(prev_state (1 j)) ! 0即城市j在prev_state中已被访问。这里state ^ (1 i)用于从当前状态中移除城市i因为i位原来是1与1异或后变为0而prev_state (1 j)用于检查城市j是否在之前的状态中。整个转移过程通过位运算高效完成。4. 避坑指南那些年我踩过的位运算的“坑”理论很美好实践起来却可能处处是坑。下面分享几个我实际编码中遇到的典型问题。4.1 移位运算的优先级陷阱位运算的优先级通常低于算术运算但高于比较运算。然而最坑的是和的优先级。错误示例if (state 1 k ! 0) { ... }你的本意是if ((state (1 k)) ! 0)。但在C中!的优先级高于所以编译器会解释为if (state (1 (k ! 0)))这完全不是你想要的意思。黄金法则只要涉及位运算尤其是与比较、算术运算混用时一律加上括号不要依赖记忆优先级。写成if ((state (1 k)) ! 0)是绝对安全的。4.2 整数类型与符号位引发的血案这是最隐蔽、最难调试的一类错误直接关系到你搜索热词中提到的“反码”和“进位”问题。场景一使用有符号int进行逻辑右移。int state -1; // 二进制表示全1补码 state state 1; // 算术右移结果还是-1高位补1 // 如果你期望的是逻辑右移高位补0得到一个大正数那就错了。解决方案状态压缩时统一使用无符号类型如unsigned intuint32_t。uint32_t state -1; state 1;会执行逻辑右移得到0x7FFFFFFF。场景二对负数进行左移。 C/C标准中对有符号整数进行左移如果结果溢出或移入符号位行为是未定义的。这意味着不同编译器、不同优化级别下可能产生不同的结果。解决方案同上使用无符号类型。场景三1 31在32位系统上的问题。 对于32位int1 31的结果是-2147483648因为最高位符号位被置为1了。这可能导致后续的位运算出现意外。解决方案使用1U 31或1LL 31如果用到64位。在定义掩码时养成使用无符号常量的习惯。4.3 循环边界与状态空间爆炸状态压缩DP之所以高效是因为它将指数级的状态用二进制数线性表示了。但这也意味着状态数仍然是2^n。当n超过20状态数超过百万时时间和空间复杂度就可能变得不可接受。在设计算法时必须清醒地认识到这一点。不要一看题目能用状态压缩就想当然去写先估算状态数 (1 n) 是否在可接受范围内通常是n 20或n 22对应百万到四百万状态。对于更大的n可能需要折半搜索Meet-in-the-Middle或其他优化技巧。4.4 忘记初始化或边界条件在状态压缩DP中dp数组通常初始化为一个很大的数如INF。初始状态例如只访问了起点城市0的dp值要设为0。循环枚举状态时通常从1开始空集状态可能单独处理。这些细节看似简单但一旦遗漏调试起来非常痛苦。建议在写代码前先在纸上画一下状态转移图明确初始状态和终止状态。5. 从理论到实践一个完整的迷你案例让我们用一个简化的问题来串联所有知识“点亮所有灯”的最少操作次数。问题描述有一个4x4的网格灯初始状态给定1亮0灭。每次按下一个灯会翻转它自身以及上下左右相邻四个灯的状态如果存在。问最少需要按多少次才能将所有灯都点亮全1如果不可能输出-1。状态压缩建模我们把4x416盏灯的状态压缩成一个16位的二进制整数state。第i位i从0到15表示第i盏灯的亮灭1亮0灭。目标状态是target (1 16) - 1即低16位全1。每个位置i的“按压操作”也可以用一个16位的掩码mask[i]来表示这个掩码中位置i及其上下左右相邻位置如果存在对应的位为1其余为0。按压操作就是让当前状态state与mask[i]进行按位异或^因为异或可以翻转特定位。问题转化为从初始状态init_state出发通过选择一系列操作掩码进行异或能否达到target求最少操作数。这等价于在2^1665536个状态中进行BFS广度优先搜索。关键步骤预处理mask[i]遍历16个位置根据其行列坐标计算上下左右邻居生成对应的掩码。BFS搜索队列存储(当前状态 操作步数)。访问数组visited[state]记录是否已访问及步数。从init_state开始对于当前状态的每一种可能操作16种计算新状态new_state state ^ mask[i]。如果new_state未访问过入队。当遇到new_state target时返回当前步数1。位运算核心整个BFS中状态转移state ^ mask[i]是O(1)的判断状态是否相等、是否为目标也都是O(1)的整数比较。这正是状态压缩高效的地方。代码片段示意核心逻辑#include bits/stdc.h using namespace std; int main() { // 1. 读入初始状态将4x4网格转换成16位整数init_state unsigned int init_state 0; for (int i 0; i 16; i) { char c; cin c; // 假设输入是16个连续的0/1字符 if (c 1) { init_state | (1U i); } } // 2. 预处理操作掩码mask[16] unsigned int mask[16] {0}; for (int i 0; i 16; i) { int r i / 4, c i % 4; mask[i] | (1U i); // 自身 if (r 0) mask[i] | (1U (i - 4)); // 上 if (r 3) mask[i] | (1U (i 4)); // 下 if (c 0) mask[i] | (1U (i - 1)); // 左 if (c 3) mask[i] | (1U (i 1)); // 右 } // 3. BFS vectorint dist(1 16, -1); // 访问数组兼记录步数 queueunsigned int q; dist[init_state] 0; q.push(init_state); unsigned int target (1U 16) - 1; while (!q.empty()) { unsigned int cur q.front(); q.pop(); int step dist[cur]; if (cur target) { cout step endl; return 0; } for (int i 0; i 16; i) { unsigned int nxt cur ^ mask[i]; // 核心状态转移异或操作 if (dist[nxt] -1) { dist[nxt] step 1; q.push(nxt); } } } cout -1 endl; // 无法达到 return 0; }通过这个案例你可以看到位运算异或、或、移位是如何紧密地嵌入到状态的定义、转移和判断中的。整个算法清晰且高效这正是二进制状态压缩的魅力所在。理解并熟练运用这些基础操作是打开状态压缩DP乃至更多底层优化技巧大门的钥匙。