1. 二进制枚举到底在解决什么问题1.1 从一个具体场景说起假设你面前有n个开关每个开关只有“开”和“关”两种状态。现在你想知道在所有可能的开关组合中哪些组合能满足某个特定条件——比如“恰好有三个开关是打开的”或者“打开的总功耗不超过某个阈值”。最直觉的做法是写n层嵌套循环每个循环遍历0和1。但n稍微大一点比如n1515层嵌套循环写出来基本没法看而且n不固定的时候根本没法写。二进制枚举就是专门对付这类问题的。它的核心思路非常朴素用一个整数的二进制位来表示一组选择状态。整数从0开始递增每个整数的二进制形式天然对应一种“选或不选”的组合。比如n3时整数0到7的二进制表示覆盖了全部8种组合十进制二进制含义0000三个都不选1001只选第1个2010只选第2个3011选第1、2个4100只选第3个5101选第1、3个6110选第2、3个7111三个都选这张表就是二进制枚举的全部秘密。你不需要写n层循环只需要写一层循环遍历0到2^n - 1然后在循环体内部用位运算检查每一位的状态。1.2 为什么大一寒假要专门练这个很多同学刚学完C语言的基本语法循环、数组、函数都知道了但遇到“从n个物品中选若干个”这类问题就卡住。暴力搜索写不出来递归还没学明白动态规划更不用提。二进制枚举恰好卡在这个位置上它不需要递归不需要复杂数据结构只需要基本的循环和位运算就能解决一大类组合搜索问题。我带过几届寒假培训发现一个规律能熟练手写二进制枚举的同学后面学递归、学状态压缩、学动态规划的时候理解速度明显快一截。原因很简单——二进制枚举是“状态压缩”思想的最原始形态。你用一个整数的每一位表示一个维度的状态这个思维模式一旦建立起来后面学状压DP就是水到渠成的事。1.3 适合谁看需要什么基础这篇内容面向的是刚学完C语言基础语法、正在放寒假的大一同学。你至少需要知道什么是整型变量int能存多大的数for循环怎么写数组的基本用法最好知道一点位运算的基础与、或、异或、左移不知道也没关系下面会补如果你已经能熟练写递归或者已经学过状压DP这篇内容对你来说可能偏基础但里面的位运算技巧和边界处理经验仍然值得扫一眼。2. 位运算基础不搞明白这几个符号后面全是坑2.1 四个必须刻在脑子里的运算符二进制枚举里高频出现的位运算只有四个但每一个都有容易踩的坑。按位与两个二进制位都是1时结果为1否则为0。用途是“检查某一位是不是1”。比如你想知道状态state的第i位是不是1就写state (1 i)结果是0说明第i位是0非0说明第i位是1。按位或|两个二进制位只要有一个是1结果就是1。用途是“把某一位置为1”。比如你想把state的第i位设为1就写state | (1 i)。按位异或^两个二进制位不同时为1相同时为0。用途是“翻转某一位”。比如state ^ (1 i)会把第i位取反。左移把二进制整体向左移动若干位右边补0。1 i生成一个只有第i位是1、其余位全是0的数。这是构造“位掩码”的标准方式。2.2 新手最容易犯的三个错误错误一把写成把|写成||。这是最致命的。是逻辑与||是逻辑或它们只返回0或1不保留位信息。你写state (1 i)结果永远是0或1根本没法判断第i位的状态。编译器不会报错但结果全错。错误二运算符优先级搞混。的优先级比低。你写if (state (1 i) 0)实际会被解析成if (state ((1 i) 0))结果完全不对。正确的写法是加括号if ((state (1 i)) 0)。我建议你养成习惯位运算表达式外面永远套一层括号。错误三左移超过类型宽度。1 31在int是32位的情况下是未定义行为因为符号位被移进去了。如果你需要枚举到2^31得用1LL 31或者用无符号类型。大一阶段n一般不超过20这个问题不突出但要知道有这回事。2.3 常用位运算操作速查下面这张表建议你抄在笔记本上做题的时候对着用操作写法说明检查第i位是否为1(state i) 1最安全的写法检查第i位是否为1state (1 i)结果非0即为1将第i位置为1state | (1 i)赋值回state将第i位置为0state ~(1 i)~是按位取反翻转第i位state ^ (1 i)0变11变0取出最低位的1state (-state)树状数组常用判断是否为2的幂state (state - 1)为0且state不为0统计1的个数__builtin_popcount(state)GCC内置函数注意__builtin_popcount是GCC编译器的内置函数在竞赛环境中可以直接用。如果是在其他编译器或者需要跨平台自己写一个循环统计也行。3. 二进制枚举的标准模板与逐行拆解3.1 最基础的模板假设有n个物品编号从0到n-1每个物品有“选”和“不选”两种状态。我们要枚举所有2^n种组合#include stdio.h int main() { int n 5; // 假设有5个物品 int total 1 n; // 2的n次方即组合总数 for (int state 0; state total; state) { // state的二进制表示就是一种组合 // 第i位为1表示选第i个物品为0表示不选 printf(组合 %d: , state); for (int i 0; i n; i) { if (state (1 i)) { printf(%d , i); } } printf(\n); } return 0; }这段代码跑出来会输出从“什么都不选”到“全选”的所有32种组合。外层循环变量state从0递增到2^n - 1每个值对应一种组合。内层循环遍历每一位检查第i位是否为1是就输出物品编号i。3.2 为什么外层循环上界是1 n1 n等于2的n次方。n个物品每个有两种状态总组合数是2^n。state从0到2^n - 1刚好覆盖所有组合。这里有个细节当n0时1 0等于1循环只执行state0一次表示“一个物品都没有只有空集这一种组合”逻辑上是自洽的。如果n比较大比如n201 20约等于100万循环100万次在1秒内能跑完。n25的话是3300万次就有点悬了。n再大就不能用二进制枚举了得换算法。一般来说二进制枚举的舒适区是n ≤ 20极限大概到n25左右再大就要考虑 meet-in-the-middle 或者其他优化。3.3 内层检查的两种写法对比检查第i位是否为1常见两种写法// 写法一先右移再与1 if ((state i) 1) { ... } // 写法二构造掩码再与 if (state (1 i)) { ... }两种写法结果完全一样。写法一的好处是不需要担心1 i溢出因为state本身就在范围内写法二更直观地表达了“检查第i位”的意图。我个人习惯用写法二但写的时候一定加括号。实际做题时两种混用也没问题关键是别写错优先级。3.4 一个完整的例子从n个数中选若干个数使和最大假设有5个数3, 7, 2, 9, 5。要求选出若干个数使它们的和最大但和不能超过15。用二进制枚举可以这样写#include stdio.h int main() { int a[] {3, 7, 2, 9, 5}; int n 5; int limit 15; int best 0; for (int state 0; state (1 n); state) { int sum 0; for (int i 0; i n; i) { if (state (1 i)) { sum a[i]; } } if (sum limit sum best) { best sum; } } printf(不超过%d的最大和是: %d\n, limit, best); return 0; }这个例子里state的每一位对应数组a中对应位置是否被选中。内层循环累加选中的数然后判断是否满足约束。这种“枚举组合检查条件”的套路是二进制枚举最典型的应用模式。4. 二进制枚举的经典应用场景4.1 子集枚举这是二进制枚举最直接的应用。给定一个集合枚举它的所有子集。比如集合 {a, b, c}所有子集是空集、{a}、{b}、{c}、{a,b}、{a,c}、{b,c}、{a,b,c}共8个。用二进制枚举state从0到7每一位对应一个元素是否在子集中。子集枚举在后续学容斥原理、子集DP的时候会反复用到。我建议你现在就把这个模板写熟做到不假思索就能敲出来。4.2 背包问题的暴力解法0-1背包问题有n个物品每个物品有重量w[i]和价值v[i]背包容量为C每个物品只能选或不选求能装下的最大价值。在学动态规划之前二进制枚举是唯一能保证正确性的解法。枚举所有2^n种选择方案对每种方案计算总重量和总价值在重量不超过C的方案中取最大价值。这个解法的时间复杂度是O(2^n * n)n20时大约2000万次操作C语言跑起来不到一秒。n25时就有点慢了但配合一些剪枝比如按价值排序后提前终止还能撑一撑。4.3 棋盘覆盖与状态压缩入门在一个n×m的棋盘上放棋子要求某些格子不能同时被选或者要求每行每列的棋子数量满足特定条件。这类问题如果n和m都很小比如n≤5可以把每一行的选择状态用一个整数的二进制位表示然后枚举行与行之间的状态转移。这就是状态压缩动态规划的雏形。我教大一学生的时候会先让他们用二进制枚举把所有行的状态组合都枚举出来暴力判断合法性。等他们写熟了再引入“只枚举合法状态”和“预处理状态转移”的优化自然过渡到状压DP。4.4 集合覆盖与任务分配有n个任务和m个人每个人能完成某些任务问最少需要几个人才能覆盖所有任务。或者反过来有n个任务每个任务需要一定时间问如何分配给两个人使总时间最接近。这类问题在n较小的时候都可以用二进制枚举来做。以任务分配为例枚举第一个人拿到的任务集合用state表示剩下的任务自然归第二个人。计算两个人的总时间取差值最小的方案。时间复杂度O(2^n * n)n20时完全可行。5. 性能优化与剪枝技巧5.1 预处理代替重复计算在上面的背包例子中内层循环每次都重新计算sum。如果n20外层100万次内层20次总共2000万次加法。其实可以利用递推关系减少计算量state的sum可以从state (state - 1)的sum加上最低位对应的值得到。int sum[1 20]; sum[0] 0; for (int state 1; state (1 n); state) { int lowbit state (-state); // 最低位的1 int idx __builtin_ctz(lowbit); // 最低位1的位置 sum[state] sum[state ^ lowbit] a[idx]; }这样每个state的sum只需要O(1)时间计算总复杂度降到O(2^n)。__builtin_ctz是GCC内置函数返回一个数二进制末尾0的个数也就是最低位1的位置。5.2 只枚举合法状态很多问题中大部分组合是不合法的。比如“选出的物品总重量不超过C”如果物品重量都很大很多组合一算就超了。这时候可以在枚举过程中提前判断或者用递归剪枝的方式只生成合法组合。但二进制枚举的优势就在于“无脑枚举”加剪枝反而可能破坏它的简洁性。我的经验是如果n≤20直接暴力枚举通常够用如果n在20到25之间再考虑剪枝或者换算法。5.3 折半枚举Meet in the Middle当n40时2^40完全不可能枚举。但可以把物品分成两半每半20个分别枚举所有组合并排序然后双指针合并。这样复杂度从O(2^40)降到O(2^20 * 20)大约2000万次操作完全可行。折半枚举是二进制枚举的自然延伸也是竞赛中处理n30到40的常用技巧。大一阶段可以先了解思路等遇到具体问题再深入。5.4 用位运算加速状态检查有些问题需要判断两个状态是否有交集、一个状态是否是另一个状态的子集。用位运算可以O(1)完成判断写法A和B是否有交集(A B) ! 0A是否是B的子集(A B) AA和B是否完全相同A BA和B是否不相交(A B) 0这些技巧在状压DP中极其常用现在先混个脸熟。6. 常见错误与调试实录6.1 数组开小了int a[1 20]在栈上开大约4MB一般没问题。但如果n251 25是3300万开int数组就是130MB栈上肯定爆。这时候要么用全局数组全局变量在堆上要么用malloc动态分配。我见过太多同学在本地跑小数据没问题一交上去就RE十有八九是数组开小了或者爆栈了。6.2 循环变量类型不对for (int state 0; state (1 n); state)中如果n311 31是负数int符号位循环条件永远不成立。n30时1 30是正数但state递增到1 30时已经接近int上限再加就可能溢出。保险做法是把state声明为long long写1LL n。6.3 位运算优先级导致的逻辑错误前面提过state (1 i) 0是错的。我再强调一遍位运算符的优先级低于比较运算符。、|、^的优先级都比、!、、低。所以任何位运算和比较混合的表达式位运算部分必须加括号。6.4 忘记处理空集有些问题要求“至少选一个”但二进制枚举从state0开始state0表示空集。如果题目不允许空集需要在循环内加判断if (state 0) continue;。这个细节很容易漏导致答案偏小。6.5 调试技巧打印二进制调试二进制枚举相关代码时把state的二进制形式打印出来非常有用void printBinary(int state, int n) { for (int i n - 1; i 0; i--) { printf(%d, (state i) 1); } printf(\n); }这样你能直观地看到每一位的状态比盯着十进制数字猜要高效得多。7. 从二进制枚举到状态压缩DP的过渡7.1 什么时候二进制枚举不够用了二进制枚举的时间复杂度是O(2^n * n)n20时约2000万次操作n25时约8亿次n30时约320亿次。当n超过25纯枚举就不可接受了。但很多问题的结构允许我们把“枚举所有组合”变成“动态规划转移”这就是状态压缩DP。7.2 一个过渡例子旅行商问题旅行商问题TSP有n个城市从城市0出发经过所有城市恰好一次最后回到城市0求最短路径。n15时二进制枚举所有排列是15!完全不可行。但用状态压缩DP状态是“当前在哪个城市”和“已经访问过哪些城市”用二进制位表示访问集合复杂度O(2^n * n^2)n15时约700万完全可行。这个例子的关键在于二进制枚举是“枚举所有状态”状压DP是“在状态之间转移”。前者是后者的基础后者是前者的优化。7.3 学习路径建议如果你现在能熟练手写二进制枚举下一步可以按这个顺序推进先练10道纯二进制枚举的题做到不看模板就能写学递归理解“选或不选”的递归写法对比二进制枚举的异同学状压DP的基础题比如“铺砖问题”“互不侵犯的国王”学折半枚举处理n30到40的情况这个路径我带过很多学生走反馈都还不错。关键是每一步都要动手写代码不能只看不练。8. 实战练习建议与刷题清单8.1 入门级练习枚举一个集合的所有子集输出每个子集的元素从n个数中选若干个数判断是否存在和为target的子集从n个数中选恰好k个数求最大和这三类题是二进制枚举的基本功建议每种写三遍以上直到能闭着眼睛敲出来。8.2 进阶级练习0-1背包的暴力解法棋盘上放棋子要求任意两个棋子不相邻任务分配问题两个人分n个任务使时间差最小这些题需要结合具体约束设计检查逻辑是二进制枚举的典型应用。8.3 挑战级练习n30的0-1背包用折半枚举n15的TSP用状压DP集合覆盖问题用二进制枚举剪枝这些题已经接近竞赛难度但核心思想仍然是二进制枚举的延伸。8.4 刷题时的注意事项我建议每道题先自己想30分钟想不出来再看题解。看题解的时候重点看“状态是怎么表示的”和“检查条件是怎么写的”而不是抄代码。抄代码只能解决一道题理解状态表示才能解决一类题。另外写完代码后一定要自己造几组小数据测试。比如n3、n4的情况手动算一下答案和程序输出对比。很多边界问题空集、全选、n0都是在小数据上暴露出来的。9. 我个人在实际教学中的几点体会带了几年寒假培训我发现二进制枚举这个知识点有个特点听的时候觉得很简单写的时候错误百出。原因不在于思路难而在于位运算的细节太多优先级、溢出、边界每一个都可能让程序跑出莫名其妙的结果。我的建议是不要追求一次写对而是养成“写完先打印中间状态”的习惯。把state的二进制形式打印出来把每次检查的结果打印出来对照着手算的结果看。调试几次之后你对位运算的直觉就建立起来了。还有一个体会是二进制枚举是检验C语言基本功的试金石。一个同学如果二进制枚举写得很顺说明他对整型、循环、数组、位运算的理解都到位了。如果写得磕磕绊绊那说明前面某个环节还有漏洞正好借这个机会补上。最后分享一个小技巧如果你实在搞不清某一位的状态就把state和掩码都写成二进制一位一位对着看。比如state5101掩码11是20105 2等于0说明第1位是0。这种“可视化”的方法虽然笨但极其有效尤其是在初学阶段。后续如果遇到n30左右的题目可以试试折半枚举如果遇到n15左右的TSP类问题可以试试状压DP。这两个方向都是从二进制枚举自然生长出来的你现在打下的基础后面都会用得上。
