Firecrawl 网页抓取与搜索 API 快速上手完整教程：4 步跑通，参数直接照抄
2026/10/1 16:46:17
其实从学习 C 语言开始，我们或多或少都学过位运算。在学过算法、读过一些源码、也学过计算机组成原理之后，我越来越觉得位运算很巧妙。
基本操作 · 集合映射 · 状压状态设计，以及 11 条容易踩中的坑
代码环境 C++11（蓝桥杯考场为 Dev-C++ 5.11，不支持 C++17/20 写法）
1：总览：什么时候该想位运算
位运算不是一个「算法」，它是一层表示法。它的用途可以归纳成一句话：
用一个整数，表示一个集合。
然后所有集合运算，都变成一次位运算。
什么时候该想到它？最可靠的信号是数据范围里的暗号。
| 题目里出现 | 信号 | 用什么 |
|---|---|---|
| 元素个数 ≤ 20，要枚举「选哪些」 | 2²⁰ ≈ 100 万，正好能开一张状态表 | 位掩码表示集合 |
| 只有 26 个小写字母 | 2²⁶太大，但「出现过哪些字母」只要 26 位 | mask 表示字符集合 |
| 状态是「已经访问过哪些点 / 拿走了哪些数」 | 集合本身就是状态 | 状压 DP |
| 问「有没有公共元素 / 是不是子集」 | 集合的比较 | 一次&搞定 |
一句话选型
看到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。
| i | 1 << i的二进制 | 十进制 |
|---|---|---|
| 0 | 0001 | 1 |
| 1 | 0010 | 2 |
| 2 | 0100 | 4 |
| 3 | 1000 | 8 |
2.3 五个基本操作
| 想做什么 | 写法 | 说明 |
|---|---|---|
| 判断第 i 位是不是 1 | mask & (1 << i) | 结果是0或1<<i，不是 0/1 |
| 置位（变 1） | mask | (1 << i) | 只动第 i 位，其他位不变 |
| 清位（变 0） | mask & ~(1 << i) | ~(1<<i)是「只有第 i 位是 0」的反向笔刷 |
| 翻转 | mask ^ (1 << i) | 翻两次回原样（x ^ k ^ k = x） |
| 取最低位的那个 1 | mask & (-mask) | 当公式记，不用推（涉及补码） |
2.4 一张能力表
把注意力放在一位上，看三个符号分别能和 0 / 1 干出什么：
| 符号 | 和1运算 | 和0运算 | 它的能力 |
|---|---|---|---|
& | x & 1 = x（保不住） | x & 0 = 0 | 能强制变 0 |
| | x | 1 = 1 | x | 0 = x（保不住） | 能强制变 1 |
^ | x ^ 1 = ~x | x ^ 0 = x | 能翻转 |
想「变 1」用|想「变 0」用&想「翻转」用^。
有了这张表，另两个操作就能自己推出来：
- 判断某一位—— 本质是「把其他位全清掉，只留目标位」。要「变 0」，所以用
&。 - 把某一位设成 1—— 要「变 1」，所以用
|。
而这两个恰好是最容易写反的一对。&和|互换之后，代码不报错，但行为完全变了：
| 写反的方式 | 实际行为 |
|---|---|
判断位用了|return mask | (1<<i); | mask | (1<<i)永远不为 0 → 转 bool 恒为true→问哪一位都回答「是 1」 |
置位用了&mask = mask & (1<<i); | 会把其他位全清 0 →不加反而删：0b1010置第 3 位后变成0b1000，bit1 被抹掉了 |
所以这张能力表值得记住——它是判断「该用哪个符号」的唯一依据，比死记四个操作可靠。
3：集合运算 → 位运算
把「集合」压成 mask 之后，集合运算全部退化成一次位运算。这张表值得背：
| 集合运算 | 位运算 | 读法 |
|---|---|---|
| 并集 | A | B | 两边有一个是 1 就是 1 |
| 交集 | A & B | 两边都是 1 才是 1 |
| 差集 | A & ~B | 从 A 里去掉 B 的元素 |
| A 是 B 的子集 | (A & B) == A | &会把 A 里「B 没有的位」清掉；清完没变就说明是子集 |
| A、B 不相交 | (A & B) == 0 | 交集为空 |
| A 是空集 | A == 0 | 一个元素都没有 |
3.1 子集判断不是万能的
一个常见的误解是：判子集就该一直用(A & B) == A。实际上要看集合被比较几次：
| 场景 | 更好的写法 | 为什么 |
|---|---|---|
| 每个集合只比一次 （LC 1684：判断每个单词的字符是否都在 allowed里） | 逐字符检查 +break | 一发现不合法的字符就退出，不用看完整个单词；而子集判据必须把整个单词压成 mask 才能判 |
| 所有 pair 都要比 （LC 318：找两个没有公共字母的单词） | 预压成 mask | n 个单词要比较 n² 对。逐字符比是O(n² × 26)；预压之后每对只要一次&→O(L + n²) |
判据
比较次数多到「不值得每次重算集合」时，就预压成 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谁赢，问先手是否必胜。
这道题要处理四件事：
| 要处理的 | 在这道题里 |
|---|---|
| 状态怎么表示 | 哪些数已经被拿走 → 一个整数 mask |
| 状态怎么变 | 拿走一个没拿过的数 i →mask | (1<<i) |
| 什么时候算赢 | 拿走 i 之后总和够到目标 → 这一步就赢；否则交给对手 |
| 怎么省重复计算 | memo[mask]：同一个局面只算一次 |
其中只有第一项是位运算的部分，其余三项都是普通的记忆化搜索写法。下面分四小节展开，重点在第一项：状态怎么定。
顺带说一个反直觉的结论：难度标签（简单 / 中等 / 困难）衡量的不是「涉及多少知识点」，而是「思路从零想出来有多难」。LC 464 官方是 Medium，因为它有一个很明确的信号（maxChoosableInteger ≤ 20）提示用状压，拿到信号之后剩下的都是固定套路。
真正 Hard 的题，难在「有一个想不到的转化」。比如 LC 887 鸡蛋掉落，关键是把问题反过来说：「k 个鸡蛋试 t 次，最多能覆盖几层楼」—— 这个转化想不到就没办法做。
4.1 状态怎么定
先不要想「用什么表示」，先问：往后会发生什么，由什么决定？
| 候选信息 | 会影响往后吗 | 结论 |
|---|---|---|
| 已拿走的数的顺序 | 不会 | 不进状态 |
| 谁拿的 | 不会（「轮到谁」由「拿了几个」决定） | 不进状态 |
| 当前总和 sum | 它不是独立信息 ——它是「哪些数被拿走了」的函数，可以直接算出来 | 不进状态 |
| 哪些数被拿走了 | 会。它决定了剩下能拿什么、还差多少 | 这就是状态 |
判断标准：把候选信息分成两类 ——
「必须交代的前提」→ 进状态；「能被算出来的答案」→ 不进状态。
sum属于第二类。而且它不进状态不只是写法问题：如果状态写成(mask, sum)，记忆化表要开2²⁰ × 300 ≈ 3 亿格，直接爆内存。
4.2 递归函数表示什么
dfs(mask)=从 mask 这个局面出发，当前要动手的那个人能不能必胜
这句话有三个直接推论：
| 推论 | 为什么 |
|---|---|
| 不需要「轮到谁」这个参数 | 函数描述的是「当前要动手的人」——谁动手，它就在说谁。两个人轮流用同一个函数，函数体一个字都不用改 |
不需要sum参数 | 它是 mask 的函数，在函数里现算就行 |
dfs(新局面)拿到的是对手的结论 | 拿走一个数，局面变成mask | (1<<i)，此时轮到对手动手。所以那个返回值说的是「对手能不能赢」 |
第三条直接决定了那个!：
对手「不能必胜」 == 我「必胜」这个!不是技巧，是上面那句定义的直接结果。（对比一下：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 两个前提
| 前提 | 结论 | 为什么 |
|---|---|---|
target <= 0 | true | 开局总和就是 0，已经达标 → 先手直接赢 |
1+2+…+m < target | false | 全部数字加起来都够不到目标 → 这局没人能赢（平局） |
第二个前提为什么必须写
转移里有「对手赢不了 ⇒ 我赢」，而平局时对手确实赢不了—— 会被误判成「我赢」。
实测：漏掉这一条，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 符号优先级类型
| # | 错误 | 后果 / 修正 |
|---|---|---|
| 2 | &和|用反 | 判断位用|→ 恒为真；置位用&→ 不加反删。回到能力表：变 1 用|，变 0 用& |
| 3 | 翻转多包一层~mask = ~(mask ^ (1<<i)) | ^本身就是「只翻转第 i 位」；外面再套~会把其他 31 位也翻一遍。实测10翻转 bit0 得到-12（正确是11），16 位下显示1111 1111 1111 0100 |
| 4 | 取位时多移一位if ((1 & (mask >> 1)) == 1) | 循环末尾已经有mask >>= 1在推进，判断里再>> 1就永远看不到 bit0。实测 9 个用例错 5 个，规律是「只要 bit0 是 1 就少算一个」。修正： if (mask & 1) |
| 5 | 数 1 的个数时传入负数countOnes(-1)死循环 | 负数右移是算术右移，符号位一直补 1，-1 >> 1还是-1。修正：参数改 unsigned（实测countOnes(-1) = 32） |
| 6 | 类内成员用()给初值vector<vector<int>> memo(21, ...); | 编译不过：error: expected identifier before numeric constant。C++ 会把它当成函数声明。类内只能写=或{}；最稳的做法是成员只声明，在入口assign |
| 7 | memset(memo, INT_MIN, sizeof(memo)) | memset是按字节填的，INT_MIN的最低字节是0x00→ 实测填出0 0 0 0。只对「每个字节都一样」的值安全：0x00(=0)、0xFF(=-1)、0x3F。其他初值用循环或vector构造函数 |
| 8 | 成员容器没在入口复位 | 同一个对象连续调用时会读到上一轮的残留值。实测：一个「返回所有子集」的函数，第二次调用得到 10 个结果（应 2 个）；一个「算博弈分差」的函数连调 2000 次，有1237 次（62%）算错。 力扣每题新建对象，所以提交页面上看不到这个错，但本地多测 / 面试 / 考场一定会出问题。这个错在多道题里都出现过 |
6.3 逻辑与语义
| # | 错误 | 后果 / 修正 |
|---|---|---|
| 9 | 优先级问题if (m[i] | m[j] == 0) | &、|、^的优先级都低于==、!=、<、>。这句会被解析成m[i] | (m[j] == 0)，基本恒为真。修正： if ((m[i] & m[j]) == 0)——位运算必须自己加括号 |
| 10 | 把mask当成summask + i >= target | mask是「位模式」，不是「那些位代表的数字之和」。实测mask = 0b0110时，mask 的数值是 6，但已拿数字之和是 3。修正：单独一个循环先算 sum |
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 在里面是什么 |
|---|---|
| LC 464 | 状压 DP：状态就是一个集合（哪些数被拿走了）+ 博弈 |
| LC 78 | mask就是子集本身（枚举所有 2ⁿ 个） |
| LC 1684 | 表示字符集合，只比一次→ 逐字符检查更优 |
| LC 318 | 表示字符集合，反复两两比较→ 必须先压好存起来 |
一句话总括：
集合 → 一个整数；集合运算 → 一次位运算；要反复比较 → 先压成 mask 存起来。
7.2 写完代码的自查清单
- 编译开
-Wall——x >> 1;那种「算了没用」的错，编译期就能抓。 - 位运算和比较混用时加括号—— 永远写
if ((a & b) == 0)，别省。 - 成员容器在入口复位——
vector/string/ 数组当返回值或缓存时，第一件事就是clear()/assign()。 - 哨兵值要选「不可能是合法答案」的—— 答案是 0/1 时，哨兵就不能是 0。
- 跑随机对拍，不只跑官方示例—— 而且要跟一份「写法不同」的实现对拍。
- 问一句：这一句「为什么对」，说得清吗？—— 说不清的部分就是隐患。