其实从学习 C 语言开始，我们或多或少都学过位运算。在学过算法、读过一些源码、也学过计算机组成原理之后，我越来越觉得位运算很巧妙。

基本操作 · 集合映射 · 状压状态设计，以及 11 条容易踩中的坑

代码环境 C++11（蓝桥杯考场为 Dev-C++ 5.11，不支持 C++17/20 写法）

1：总览：什么时候该想位运算

位运算不是一个「算法」，它是一层表示法。它的用途可以归纳成一句话：

用一个整数，表示一个集合。

然后所有集合运算，都变成一次位运算。

什么时候该想到它？最可靠的信号是数据范围里的暗号。

一句话选型

看到20或26，先想「是不是要用一个整数装一个集合」。 然后问：这个集合是要反复比较，还是只比一次？这决定了要不要预存。(其实有时候也可以用哈希表)

2：五个操作 + 一张能力表

2.1 一个int就是32个开关

25 的二进制 = 0000 0000 0000 0000 0000 0000 0001 1001 ↑↑↑ ↑ bit4=1, bit3=1, bit0=1

约定：bit 0是最右边那一位（最低位），往左依次bit 1、bit 2……

这一条是所有位运算的地基，也是最别扭的地方——写代码时脑子里要「从右往左数」。

2.2 一个单格操作1<<i

1 << i就是一个「只有第 i 位是 1、其他位全是 0」的数，等于2^i。

2.3 五个基本操作

2.4 一张能力表

把注意力放在一位上，看三个符号分别能和 0 / 1 干出什么：

想「变 1」用|想「变 0」用&想「翻转」用^。

有了这张表，另两个操作就能自己推出来：

• 判断某一位—— 本质是「把其他位全清掉，只留目标位」。要「变 0」，所以用&。
• 把某一位设成 1—— 要「变 1」，所以用|。

而这两个恰好是最容易写反的一对。&和|互换之后，代码不报错，但行为完全变了：

所以这张能力表值得记住——它是判断「该用哪个符号」的唯一依据，比死记四个操作可靠。

3：集合运算 → 位运算

把「集合」压成 mask 之后，集合运算全部退化成一次位运算。这张表值得背：

3.1 子集判断不是万能的

一个常见的误解是：判子集就该一直用(A & B) == A。实际上要看集合被比较几次：

判据

比较次数多到「不值得每次重算集合」时，就预压成 mask。只比一次的话，「逐字符 + 早退出」反而更快。

3.2 LC318的完整写法

题目：找两个没有公共字母的不同单词，使长度之积最大。

class Solution { public: int maxProduct(vector<string>& words) { int n = words.size(); // ① 预压：每个单词 → 一个 26 位的 mask vector<int> m(n, 0); for (int i = 0; i < n; i++) for (char c : words[i]) m[i] |= 1 << (c - 'a'); int ret = 0; for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) if ((m[i] & m[j]) == 0) // ② 交集为空 = 没有公共字母 ret = max(ret, (int)(words[i].size() * words[j].size())); return ret; // ③ 长度直接取 size() } };

这段代码里有三处高频错误，都收进了后面的清单：

• 把&写成|（并集 vs 交集）
• 想用「数 mask 里 1 的个数」当长度——重复字母会丢（"aaa"长度 3，但只有 1 个 1）
• 判断语句没加括号，撞上优先级问题（见清单第 9 条）

4：位掩码当状态：一道题的完整拆解（看不懂可以先看5）

LC 464 我能赢吗：从1..maxChoosableInteger里轮流取数（取过不能再取），谁先让累计和 ≥desiredTotal谁赢，问先手是否必胜。

这道题要处理四件事：

其中只有第一项是位运算的部分，其余三项都是普通的记忆化搜索写法。下面分四小节展开，重点在第一项：状态怎么定。

顺带说一个反直觉的结论：难度标签（简单 / 中等 / 困难）衡量的不是「涉及多少知识点」，而是「思路从零想出来有多难」。LC 464 官方是 Medium，因为它有一个很明确的信号（maxChoosableInteger ≤ 20）提示用状压，拿到信号之后剩下的都是固定套路。

真正 Hard 的题，难在「有一个想不到的转化」。比如 LC 887 鸡蛋掉落，关键是把问题反过来说：「k 个鸡蛋试 t 次，最多能覆盖几层楼」—— 这个转化想不到就没办法做。

4.1 状态怎么定

先不要想「用什么表示」，先问：往后会发生什么，由什么决定？

判断标准：把候选信息分成两类 ——

「必须交代的前提」→ 进状态；「能被算出来的答案」→ 不进状态。

sum属于第二类。而且它不进状态不只是写法问题：如果状态写成(mask, sum)，记忆化表要开2²⁰ × 300 ≈ 3 亿格，直接爆内存。

4.2 递归函数表示什么

dfs(mask)=从 mask 这个局面出发，当前要动手的那个人能不能必胜

这句话有三个直接推论：

第三条直接决定了那个!：

对手「不能必胜」 == 我「必胜」

这个!不是技巧，是上面那句定义的直接结果。（对比一下：LC 486 用「分数」表示，写的是x − 对手的分差；这道题用「胜负」表示，写的是!dfs(...)。同一个意思，两种写法。）

4.3 完整代码

class Solution { int m, target; vector<int> memo; // memo[mask]：-1 没算过 ／ 0 输 ／ 1 赢 public: bool canIWin(int maxChoosableInteger, int desiredTotal) { m = maxChoosableInteger, target = desiredTotal; memo.assign(1 << (m + 1), -1); // 入口复位；位号用 1..m，所以开 m+1 位 if (target <= 0) return true; // 前提一 if ((long long)m * (m + 1) / 2 < target) return false; // 前提二 return dfs(0); // 起始局面：一个数都没拿 } bool dfs(int mask) { if (memo[mask] != -1) return memo[mask]; // ① 查表 int sum = 0; // ② sum 从 mask 推出来 for (int i = 1; i <= m; i++) if (mask & (1 << i)) sum += i; for (int i = 1; i <= m; i++) { // ③ 试每一个还没拿的数 if (mask & (1 << i)) continue; if (sum + i >= target) // 分支 A：这一手就赢 return memo[mask] = 1; if (!dfs(mask | (1 << i))) // 分支 B：对手赢不了 → 我赢 return memo[mask] = 1; } return memo[mask] = 0; // ④ 都赢不了 } };

4.4 两个前提

第二个前提为什么必须写

转移里有「对手赢不了 ⇒ 我赢」，而平局时对手确实赢不了—— 会被误判成「我赢」。
实测：漏掉这一条，m=1、T=2..13这一整片的结论都会反过来。

5：学习顺序：零件->半步->综合

上面这些内容，按「零件 → 半步 → 综合」三层来学，会比直接啃综合题快很多。

① 零件 把知识点拆成最小的操作，逐个写、逐个验证 位运算的零件：判断 / 置位 / 清位 / 翻转 / 数 1 的个数 / 打印二进制 ② 半步 只综合【本次学的零件】，不引入任何旧知识 位运算的半步：用 mask 打印所有子集（不涉及 DP、记忆化、博弈） ③ 综合 零件 + 旧知识 LC 464 = 位掩码 + 记忆化 + 博弈

只做 ① 和 ③ 的话，最容易卡在 ③。因为「会写零件」和「能把零件拼成一道题」是两种不同的能力，中间还差一层。

5.1 第一步：把五个操作数写成函数

位运算的零件就是 2.3 节那五个操作。要求很简单：每个都单独写成一个函数，并且单独验证。

void printBinary(int x, int bitsize = 32); // 把一个数打成二进制 bool getBit(int mask, int i); // 判断第 i 位 void setBit(int& mask, int i); // 第 i 位置 1 void clearBit(int& mask, int i); // 第 i 位清 0 void flipBit(int& mask, int i); // 第 i 位翻转 int countOnes(unsigned mask); // 数有几个 1

其中printBinary看起来最简单，但最值得先写 —— 后面每个操作都要用它来核对结果。

#pragma once #include <iostream> using namespace std; //打印2进制 void printBinary(int x, int bitsize = 32) { for (int i = bitsize-1; i >= 0; i--) { cout << ((x >> i) & 1); if (i % 4 == 0 && i > 0) cout << ' '; } cout << endl; } //判断mask的第i位是不是1 //从低位到高位 bool getBit(int mask, int i) { return mask & (1 << i); } //把mask的第i位设成1 void setBit(int& mask, int i) { mask = mask | (1 << i); } void cleanBit(int& mask, int i) { mask = mask & ~(1 << i); } // 把 mask 的第 i 位翻转（0→1，1→0） void flipBit(int& mask, int i) { mask = mask^(1 << i); } // 数一数 mask 里有几个 1 int countOnes(unsigned int mask) { int count = 0; while (mask) { if ((1 & mask ) == 1) { count++; } mask >>= 1; } return count; }

5.2 第二步：先用mask打印所有子集

五个操作都写熟之后，直接来做 LC 464，可能还是没法下手。这时候缺的不是再讲一遍状态设计，而是一个不涉及 DP、不涉及记忆化、不涉及博弈的小程序。

最合适的就是：打印n个元素的全部子集。

元素编号 0、1、2 一个 mask 就代表一个子集 mask = 0 000 { } mask = 1 001 { 0 } mask = 2 010 { 1 } mask = 3 011 { 0, 1 } mask = 4 100 { 2 } mask = 5 101 { 0, 2 } mask = 6 110 { 1, 2 } mask = 7 111 { 0, 1, 2 }

程序本身只有两层循环：

// 把一个数字翻译成"选中了哪些元素" // mask : 那个数字（比如 5） // n : 一共有几个元素，编号 0 ~ n-1（比如 3） void printSet(int mask, int n) { cout << "{ "; for (int i = 0; i < n; i++) // 逐位检查：第 0 位 → 第 1 位 → ... → 第 n-1 位 { if (getBit(mask, i)) // getBit 返回非 0 → 那一位是 1 → 元素 i 被选中 { cout << i << " "; } } cout << "}" << endl; }

为什么这 6 行值得单独练

它正好是状压 DP 的前半截：
· 外层for (mask ...)=把所有 2ⁿ 个局面走一遍
· 内层mask & (1<<i)=从一个局面里读出「现在是什么情况」
剩下的（做决策 + 存结果）才是 DP。先把这半截跑通，「mask 就是一个集合」就清楚了。

做完这张表之后，LC 464 剩下的只是：在每个局面上试每个选择、把结果缓存起来 —— 而这部分就是普通的记忆化搜索写法。

5.3 三层的关系

另外，动手做综合题之前先列零件清单：

这道题需要几个零件？其中几个是没见过的？

没见过≥ 2 个→ 先拆开练零件，不要直接做。

6：易错清单

以下 11 条全部来自实测，附错误代码、后果、修正。它们的共同点是：代码都能编译，有的甚至能通过官方样例。

6.1 算了但没接住

第 1 条x >> 1;单独成句 = 什么都没干

while (x) { cout << (x & 1); x >> 1; // ← 算了一下，然后扔掉 }

实测x做完三次还是原来的值 →死循环。要改 x 就必须写x >>= 1;。
用-Wall编译会直接报statement has no effect—— 这个错不该留到运行期。

这个错在两类任务里都会出现（打印二进制、数 1 的个数）。值得变成一个条件反射：

写x >> 1、x + 1、x | y这种单独成句的时候，先问一句 ——

「是改 x，还是只看一眼？」

要改 →必须有=；只看 → 结果必须被用掉。

6.2 符号优先级类型

6.3 逻辑与语义

6.4 「能过但不对」

第 11 条mask += i—— 能 AC，但只是碰巧

int mask = 0; for (int i = 0; i < pow(2, n); i++) { mask += i; // ← 想要的是 mask = i check(mask, nums); }

mask += i得到的是三角数0, 1, 3, 6, 10, 15, 21, 28, …，不是0..2ⁿ-1。

但它居然能 AC。实测：T_i mod 2ⁿ恰好是0..2ⁿ-1的一个排列（n=1..16 全部成立），而mask & (1<<i)只看低 n 位 ——等价于取模，所以结果集合完全正确。

（改成mask += 1同样能 AC，因为1,2,…,2ⁿ-1,0的低 n 位还是一个排列。）

代码里「说不清为什么对、但结果对」的部分，是隐患。

只要循环起点一改、检查方式一改、范围一改，立刻全错，而且不知道该往哪查。

「能过」不是标准，「能说清它为什么对」才是标准。

同类案例：拓扑排序里有向边建反了，但「有没有环」这个判断对方向不敏感，所以照样 AC。换一道要求输出具体顺序的题，同一张反图 1651 个无环用例里997 个（60%）非法。

这说明：验证模型的办法，是拿去解要求更细的姊妹题。只跑官方示例不算验证。

7：总结

7.1 四种用法

把「用 mask 表示集合」的四种用法排一下，基本就覆盖完了：

一句话总括：

集合 → 一个整数；集合运算 → 一次位运算；要反复比较 → 先压成 mask 存起来。

7.2 写完代码的自查清单

1. 编译开-Wall——x >> 1;那种「算了没用」的错，编译期就能抓。
2. 位运算和比较混用时加括号—— 永远写if ((a & b) == 0)，别省。
3. 成员容器在入口复位——vector/string/ 数组当返回值或缓存时，第一件事就是clear()/assign()。
4. 哨兵值要选「不可能是合法答案」的—— 答案是 0/1 时，哨兵就不能是 0。
5. 跑随机对拍，不只跑官方示例—— 而且要跟一份「写法不同」的实现对拍。
6. 问一句：这一句「为什么对」，说得清吗？—— 说不清的部分就是隐患。