位运算 知识点讲解

位运算直接对整数在内存中的二进制位进行运算——不是把数当成一个整体算，而是把它拆成一排 0 和 1，一位一位地算。

📌 怎么读这份讲义：位运算难的不在"算"，而在"看到题目能想到用它"。所以本文把「什么时候该想到位运算」放在最前面，每道例题也都按「审题 → 思路 → 代码 → 解读」五步拆开讲——重点永远是：怎么从题目文字想到用它、怎么落地写代码。

概念

位运算（bitwise operation）是直接对整数的二进制位（bit，每一个 0 或 1）进行运算的操作。

计算机里所有整数都是以二进制存储的。比如：十进制 6 是 110，十进制 3 是 011。普通的四则运算是对"整个数"算，而位运算是把两个数的每一位上下对齐，逐位计算。例如 6 & 3：

  1 1 0   (6)
& 0 1 1   (3)
---------
  0 1 0   = 2

所以 6 & 3 == 2。

核心原理（六个运算符 + 异或三性质）

C++ 里一共有 6 个位运算符，记住它们各自"按位干什么"即可：

最值得记住的 3 条异或性质（后面例题全靠它）：

1. a ^ a = 0（一个数和自己异或，抵消成 0）

2. a ^ 0 = a（和 0 异或，原数不变）

3. 异或满足交换律、结合律：a ^ b ^ c == a ^ c ^ b，顺序随便换

顺带一提：一串 0 和 1 在题目里常有两种看法——看成"一排开关"（第 k 位是 1 还是 0，就是第 k 个开关开/关，用来取位、改位、翻转位），或看成"一个集合"（第 k 位是 1 表示集合里有第 k 号元素，用来做"选或不选"的状态压缩）。后面「定义」一节会把六个运算符一个一个拆开，逐位走查一遍——那是所有写法的依据。

四个高频坑

这四条是写位运算时最容易出错的地方，具体例子见文末「常见错误」。

• & 不是 &&，| 不是 ||：&& / || 是逻辑运算，只出"真 / 假"，还会短路；& / | / ^ 是逐位运算，每一位都算一遍。条件判断里写成 if (x & y) 是另一件事。
• >> 不等于"永远等于除以 2"：n >> 1 当除以 2 只在 n ≥ 0 时确定成立。稳妥的初学原则是位运算只用于非负整数。
• ~n 不是"你以为的那个正数"：补码下 ~n == -n - 1，~5 是 -6 而不是 2；初学阶段 ^ 用得多，~ 主要用于拼"把某一位清 0"的掩码。
• 移位会溢出：1 << 31 在 int 里变负数，1 << 40 直接溢出，高位一律写 1LL << k。

方向上的提醒：位运算只适合"能化成对 0/1 位操作"的问题，硬套反而更难懂——先看题面特征决定用不用，下一节就是判据。

【最重要】看到这些信号，第一时间想到位运算

这是整篇讲义的核心判断标准。做题时，只要题干出现下面这些关键词 / 条件 / 特征，就要立刻在脑子里亮红灯："这道题可能要用位运算！"

记住一句话：位运算的精髓不是"算得快"，而是"把题目的某些条件翻译成对 0/1 位的操作"。上面这张表就是你的"审题触发清单"。后面「写法总表」和「编程题用法」会把它展开成更细的招式。

定义

第 k 位怎么数

二进制位从最右边开始数：最右边一位是第 0 位，往左依次是第 1 位、第 2 位……第 k 位的权值是 2^k。以 13 为例：

把有 1 的几位的权值加起来：8 + 4 + 0 + 1 = 13。所以"13 的二进制是 1101"的意思是：13 里含一个 8、一个 4、一个 1，不含 2。

位数从 0 开始数，第 k 位的权值是 2^k。本节后面的公式都按这个约定。

一个 int 固定占 32 位，编号是第 0 位到第 31 位；long long 占 64 位。位运算就在这固定的一排格子里做，格子数是定死的——后面讲取反、讲溢出，都要用到这一点。

六个运算符逐位走查

六个运算符的「逐位规则」和「一句话记忆」已在「概念 · 核心原理」表里给过，这里不再重复列表，而是把每个运算符逐位走查一遍——这是后面所有写法的依据，务必看熟。

下面用 5 和 3 做例子（5 = 0101，3 = 0011）。两串 0 和 1 上下对齐，一位一位单独计算，位与位之间互不影响，也不进位、不借位。

按位与 &

5 & 3：

5 = 0 1 0 1
3 = 0 0 1 1
──────────── &
    0 0 0 1   = 1

四位里只有最低位"都是 1"，其余三位各有一个 0，所以结果只剩最低位的 1。

按位与常用来判断某一位是不是 1（n & 1 判断奇偶）、把某一位清成 0（n & ~(1<<k)），以及求两个数共同的 1 位（a & b）。

按位或 |

5 | 3：

5 = 0 1 0 1
3 = 0 0 1 1
──────────── |
    0 1 1 1   = 7

按位或常用来把某一位置成 1（n | (1<<k)），或把两个集合合并（各自为 1 的位合起来）。

按位异或 ^

5 ^ 3：

5 = 0 1 0 1
3 = 0 0 1 1
──────────── ^
    0 1 1 0   = 6

由此得到两条性质。一是 a ^ a = 0：同一个数上下对齐做异或，每一位都和自己相同，而"相同得 0"，所以每一位都是 0：

a = 0 1 1 0
a = 0 1 1 0
──────────── ^
    0 0 0 0

二是 a ^ 0 = a：0 的每一位都是 0，而"与 0 异或保持原样"，所以结果还是 a。这两条就是后面"成对抵消"的全部依据。

按位异或常用来翻转某一位（n ^ (1<<k)）、找出只出现一次的数（成对的会互相抵消），以及交换两个数（不用临时变量）。

按位取反 ~

按位取反只作用于一个数，把它在这一排格子里的每一位都换掉：0 变 1，1 变 0。先在 4 位上看：

 5  = 0 1 0 1
~5  = 1 0 1 0

int 是 32 位，所以 C++ 里的 ~5 是对 32 位整体取反：

5   = 0000 0000 0000 0000 0000 0000 0000 0101
~5  = 1111 1111 1111 1111 1111 1111 1111 1010   = -6

结果是 -6，因为 32 位里最高位（第 31 位）是 1 的数代表负数。负数怎么读：把它取反再加 1，就得到它的相反数，也就是 -n = ~n + 1（这条规则叫补码）。拿 4 位验证 1010：取反得 0101，加 1 得 0110，而 0110 正是 6，所以 1010 就是 -6。4 位里的 ~5 也是 1010，两处对上了 —— ~5 = -6 和公式 ~n = -n - 1 说的是同一件事。

按位取反常用来得到"除第 k 位是 0、其余全为 1"的掩码 ~(1<<k)，再配合 & 把第 k 位清 0。要注意 ~ 取反的是整个整数，不是指定位；如果只想翻转第 k 位，应先用 1 << k 得到只覆盖一位的掩码，再用 ^ 翻转。

左移 <<

5        = 0 1 0 1
5 << 1   = 1 0 1 0      = 10   （左边超出的位丢掉，右边补 0）
5 << 2   = 1 0 1 0 0    = 20

每左移一位，每个 1 的权值变为原来的 2 倍，所以 n << k 就是 n * 2^k。

右移 >>

13        = 1 1 0 1
13 >> 1   = 0 1 1 0     = 6   （13 ÷ 2 = 6.5，向下取整为 6）
13 >> 2   = 0 0 1 1     = 3

正数右移，左边空出的高位补 0；右边移出的位直接丢掉，相当于整除 2^k 并向下取整。

左移 k 位就是乘 2^k，右移 k 位就是除以 2^k（向下取整）。配合"位数从 0 数起、第 k 位权值是 2^k"，后面所有写法都从这里来。

图示

下图是左移、右移的示意：位移就是二进制位整体平移（左移时高位丢弃、低位补 0；右移相当于除以 2 的幂并向下取整）。

& 挑出"都是 1"的位，| 挑出"至少有一个 1"的位，^ 挑出"不同"的位，~ 把每一位取反，<< 和 >> 把整串平移。把其中一个动作固定到第 k 位上，就是 1 << k —— 一张只覆盖第 k 位的掩码。

只覆盖第 k 位的掩码

1 的二进制只有最低位是 1，其余全是 0。左移 k 位，那个 1 就走到第 k 位：

1       = 0000 0001
1 << 2  = 0000 0100    ← 第 2 位变成 1，别的位置还是 0
1 << 3  = 0000 1000    ← 第 3 位变成 1

所以 1 << k 永远是一个"只有第 k 位是 1、别的位置全是 0"的数。它像一张模板，拿去和原数做运算就只影响第 k 位：| 把它置 1，& 配合取反把它清 0，^ 把它翻转，& 单独看它原来是 1 还是 0。

抹掉最低位的 1：n & (n-1)

减 1 动的是二进制最右边的那个 1：它自己变成 0，它右边的 0 全变成 1。以 12 为例：

 12     = 1 1 0 0
 12 - 1 = 1 0 1 1     ← 最低位的 1 变 0，它右边的两个 0 变 1
────────────── &
          1 0 0 0     = 8

再抹一次，8 就归零：

 8     = 1 0 0 0
 8 - 1 = 0 1 1 1
────────────── &
         0 0 0 0

12 的二进制里有两个 1，两次就抹干净了。所以 n & (n-1) 每做一次少一个 1，做到 0 为止，做的次数就是 n 里 1 的个数。同一个道理也用来判定 2 的幂：2 的幂只有一个 1，做一次就归零。

留下最低位的 1：n & -n（lowbit）

-n 按上面的补码规则等于 ~n + 1。把它和 n 逐位对起来，关键在 n 最低位的那个 1：

• 这个 1 的右边全是 0，取反后全是 1；加 1 时一路进位，右半边又回到全 0，而那个 1 取反得 0、被进位补成 1。所以"最低位的 1 及其右边"这一段，-n 和 n 完全一样。
• 这个 1 的左边，进位到这一位就停了，-n 就是 n 取反后的样子，每一位都跟 n 相反，与起来全是 0。

以 12 为例（多写一位当符号位）：

 12 = 0 1 1 0 0
-12 = 1 0 1 0 0     ← ~12 + 1
────────────── &
      0 1 0 0       = 4     ← 正好是 12 最低位的那个 1

所以 n & -n 只留下最低位的那个 1，其余全归 0。它有个名字叫 lowbit，常见写法 x & -x。

优先级（必看，超容易错）

位运算的优先级很低，而且相互之间也有高低。一张表记住排序（从高到低）：

~ （单目，最高）
<<  >>
&
^
|        （最低）

关键结论：位运算的优先级全都低于 + - * /、==、<、&&、|| 等。

铁律：凡是用位运算写条件，外层一律加括号。比如 (n & 1)、(n >> k) & 1、(n & (n-1)) == 0，一个都别省。 少加一层括号会怎样——if (a & 1 == 0) 被理解成 a & (1 == 0) 即 a & 0，永远为假。文末「常见错误」第 1 条有对照写法。

数据范围与溢出（int / long long）

• int 是 32 位（其中 1 位是符号位，余下 31 位表示数值），范围约 [-2.1e9, 2.1e9]；long long 是 64 位，范围约 ±9e18。
• 移位溢出陷阱：1 << 31 在 int 里会溢出成负数（因为第 31 位是符号位），这是未定义行为。要表示 2³¹ 必须写 1LL << 31（1LL 是 long long 类型的 1）。
• 移位位数不能 ≥ 类型的位数：1 << 32 对 int 是错的。需要大数就用 long long。
• 题目数据到 1e9 量级时 int 够用；到 1e18 量级或涉及 2^k（k 较大）时，一律上 long long + 1LL << k。
• 初学阶段位运算只用于非负整数：虽然 GCC 下负数右移是确定的算术右移（-4>>1 得 -2），但写上更通用、更稳，也避开"以为它永远等于除以 2"的误解（详见 常见错误）。

C++ 内置位运算函数（GCC / 评测环境支持）

这些不是"必须学"，但能省事，CSP-J 评测环境（GCC/Clang）都支持：

注意参数类型：__builtin_popcount 吃 unsigned int，传 long long 要用 popcountll，否则高位会被截断。

常见技巧速查表（背下来）

把上面六条运算符和掩码组合起来，就得到下面这些"拿到题就能直接写"的定式。建议背熟——它们是位运算题 90% 的落笔处：

这张表和前面「【最重要】看到这些信号」的触发清单是配套的：触发清单告诉你"题目里出现什么该想到位运算"，这张表告诉你"想到之后具体怎么写"。两者一起用，从读题到落笔就通了。

编程题用法：12 个用法

例题

下面每道例题都固定按五节来写：题目描述 → 审题分析（核心）→ 解题思路 → C++ 参考代码 → 代码解读。前两道是基础中的基础，后面两道是进阶。

例 1 · 唯一出现一次的数（异或去重）

【题目描述】 给定一个长度为 n 的数组，其中除了一个数字只出现一次之外，其他每个数字都恰好出现两次。请找出那个只出现一次的数字。 - 限制：1 ≤ n ≤ 10^5，数组元素为 int 范围。 - 要求：时间复杂度 O(n)，空间复杂度 O(1)。 - 输入：第一行 n，第二行 n 个整数。 - 输出：那个只出现一次的数字。

【审题分析（核心）】 ① 读题抓条件： 条件 A——只有一个数字出现一次；条件 B——其余每个数字都"恰好出现两次"；条件 C——要求 O(1) 额外空间（不能用额外的数组/哈希表来记次数）。 ② 找出题目的需求： 从一堆数里，把那个"落单"的数挑出来。 ③ 判断为什么能用位运算（突破口）： 关键信号是条件 B 的"出现两次 / 两两成对"。这正好命中异或性质——a ^ a = 0（相同的两个数异或会抵消成 0）。如果我们把所有数依次异或一遍，成对出现的数会两两抵消变成 0，最后剩下的就是那个只出现一次的数。 ④ 如果不用位运算会怎样（对比凸显位运算的价值）： 方案 1 用 map / 数组统计次数 → 空间 O(n)，不满足 O(1)；方案 2 先排序再找 → 时间 O(n log n)，不如位运算的 O(n) 干净。位运算一遍遍历异或，时间 O(n)、空间 O(1)，完美契合题目要求。 ⑤ 梳理解题思路（算法步骤）： 设 ans = 0（因为 a ^ 0 = a，0 是异或的"单位元"）；从左到右把每个数 x 执行 ans ^= x；遍历结束，ans 里成对的数已全部抵消为 0，只剩落单的那个数；输出 ans。

【解题思路】（完整算法流程） `` 输入 n ans = 0 循环 i = 0 .. n-1: 读入 x ans = ans ^ x 输出 ans ` 利用异或的交换律、结合律，顺序无关紧要；利用 a^a=0、a^0=a`，成对抵消后结果即答案。

【C++ 参考代码】 ``cpp #include <iostream> using namespace std; int main() { int n; cin >> n; int ans = 0; // 异或的单位元是 0：任何数 ^0 都等于它本身，所以初始放 0 不会破坏结果 for (int i = 0; i < n; i++) { int x; cin >> x; ans ^= x; // 把当前这个数异或进 ans；成对的數会两两抵消（a^a=0） } // 循环结束后：出现两次的数互相抵消为 0，最后 ans 里只剩下那个"只出现一次"的数 cout << ans << endl; return 0; } ``

【代码解读】（逐段对应位运算用法） - int ans = 0;：对应异或性质 a ^ 0 = a。用 0 当初始值，保证第一个数异或后"原样留下"。 - for 循环里的 ans ^= x;：对应异或性质 a ^ a = 0 以及交换律、结合律。因为异或顺序随意，所有"出现两次"的数最终会两两配对抵消成 0，只有落单的那个数没被抵消，孤零零留在 ans 里。 - 本题用到的核心位运算：^ 异或，以及它的三条性质。这就是"看到'成对/出现两次/去重'就想到异或"的典型范例。

例 2 · 统计二进制中 1 的个数（n&(n-1)）

【题目描述】 给定一个正整数 n（1 ≤ n ≤ 2×10^9），求它的二进制表示中 1 的个数。 - 多组输入：每行一个 n，直到文件结束。 - 输入：每行一个正整数 n。 - 输出：对应每个 n，输出其二进制中 1 的个数，每行一个。

【审题分析（核心）】 ① 读题抓条件： 条件 A——求"二进制表示中 1 的个数"（popcount）；条件 B——数据范围到 2×10^9，在 int 范围内；条件 C——多组输入。 ② 找出题目的需求： 数出一个数写成二进制后，一共有几个位是 1。 ③ 判断为什么能用位运算（突破口）： 关键词是"二进制中 1 的个数"。这直接命中 n & (n - 1) 技巧——n & (n-1) 能正好消去 n 二进制里"最低位的一个 1"。每消去一个 1 我们就计一次数，直到 n 变成 0，计数就是答案。循环次数 = 1 的个数（最多 31 次），比"转字符串再数"快得多也稳得多。 ④ 如果不用位运算会怎样： 方案是不断除以 2 取余数看是否为 1 来计数（while(n){ if(n%2==1) cnt++; n/=2; }）。这也能做，但本质是"模拟二进制"，不如 n & (n-1) 优雅、且循环次数一样。位运算写法更短、更不容易写错，也是竞赛里的标准写法。（也可直接用内置函数 __builtin_popcount(n) 一步得到。） ⑤ 梳理解题思路（算法步骤）： 初始化 cnt = 0；只要 n > 0：n = n & (n - 1)（消去最低位的一个 1），cnt++；当 n 变为 0 时停止，cnt 即为 1 的个数。

【解题思路】（完整算法流程） `` 当还有输入 n 时: cnt = 0 while n > 0: n = n & (n - 1) // 消去最低位的一个 1 cnt = cnt + 1 输出 cnt ` 为什么 n & (n-1) 能消最低位 1？举例：n = 12（1100），n-1 = 11（1011），1100 & 1011 = 1000`（即 8），最低位的那个 1 被消掉了，其余位不变。反复做，1 就被一个一个消光。

【C++ 参考代码】 ``cpp #include <iostream> using namespace std; // 方法一：用 n & (n-1) 逐个数（最推荐，能体现位运算思想） int countOne(int n) { int cnt = 0; while (n > 0) { n = n & (n - 1); // 每次把 n 二进制里"最低位的一个 1"变成 0，其余位保持原样 cnt++; // 每消去一个 1，计数 +1 } return cnt; // 循环结束（n 变 0）时，cnt 就是 1 的个数 } int main() { int n; while (cin >> n) { // 多组输入，读到文件结束 cout << countOne(n) << endl; } return 0; } ` 附：一行搞定的内置函数写法（GCC 评测环境可用） `cpp int main() { int n; while (cin >> n) { cout << __builtin_popcount((unsigned int)n) << endl; // 直接返回二进制中 1 的个数 } return 0; } ``

【代码解读】（逐段对应位运算用法） - n = n & (n - 1);：本题核心，对应技巧"消去最低位的一个 1"。原理——n-1 会把 n 中最低位的那个 1 及其右边的所有 0 全部翻转，于是 n & (n-1) 只把那一个 1 变成 0。 - cnt++;：每成功消去一个 1 就记一次，循环次数严格等于 1 的个数（最多 31 次），效率极高。 - 对照写法 __builtin_popcount：本质就是编译器帮我们做了一遍上面的循环，理解原理后直接用也无妨。 - 本题用到的核心位运算：& 按位与 + n & (n-1) 消低位 1 技巧，背后是 lowbit 思想。

例 3 · 两个落单的数（异或分组）

数组里只有两个数各出现一次、其余都出现两次，要找出这两个数。这题是例 1 的升级：全部异或一遍得到 x ^ y（成对的归零），再按它们最低的不同位分成两堆，各自异或就能拆出两个答案。

#include <cstdio>
const int N = 1000005;
int a[N];

int main() {
    int n;
    scanf("%d", &n);
    int d = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        d ^= a[i];                     // 全部异或完，成对的归零，只剩 x ^ y
    }
    int low = d & -d;                  // 取 x 与 y 最低的不同位，拿它当分组依据
    int x = 0, y = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] & low) x ^= a[i];     // 这一位是 1 的，进第一堆
        else            y ^= a[i];     // 这一位是 0 的，进第二堆
    }
    printf("%d %d\n", x, y);
    return 0;
}

审题要点： 题面信号同样是"出现两次 / 找落单的"，所以先想异或；但"落单的有两个"时，一次异或只能得到 x^y，必须再找一个"能把两数分开"的位——d & -d（lowbit）正好给出最低的不同位，两个数必然落在不同侧，同侧其余元素仍两两成对，第二遍各自异或各剩一个。两遍扫描 O(n)；因为要看两遍，输入得先存下来。

例 4 · 把 n 个数分成两组（二进制枚举）

n ≤ 20 时 2²⁰ ≈ 100 万，可以直接把"每个数分到哪一组"压成整数 S 的一位——这就是"整数即集合"最朴素的样子：

#include <iostream>
using namespace std;
int a[20];

int main() {
    int n;
    cin >> n;
    int total = 0;
    for (int i = 0; i < n; i++) { cin >> a[i]; total += a[i]; }

    int best = total;
    for (int S = 0; S < (1 << n); S++) {       // 2^n 种分法，一种不漏
        int s = 0;
        for (int k = 0; k < n; k++)
            if ((S >> k) & 1) s += a[k];       // 第 k 位是 1，第 k 个数进第一组
        int diff = total - 2 * s;              // 两组之差 = |总和 - 2×(第一组的和)|
        if (diff < 0) diff = -diff;
        if (diff < best) best = diff;
    }
    cout << best << endl;
    return 0;
}

审题要点： 题面出现 "n ≤ 20""每样选或不选""用没用过"，第一时间想到"整数即集合"——S 的第 k 位是 1 就把第 k 个数划进第一组。S 从 0 走到 (1 << n) - 1，2^n 种分法刚好走完一遍，不重不漏；每种分法花 O(n) 把第一组的和加出来，总复杂度 O(n·2^n)，n = 20 时约 2000 万次，能过。

例题复盘总结（统一汇总）

前面两道基础例题（例 1 异或去重、例 2 数 1 的个数）都用"审题五段式"拆开讲过，这里把它们放在一起归纳，把"怎么想"收个口。例 3（两个落单）是例 1 异或分组的进阶，例 4（二进制枚举）是"整数即集合"的入门——它们同样遵循下面这条审题模板。

1. 两道题分别用到的位运算技巧

• 例 1（异或去重）： 运算符 ^ 异或；技巧 a ^ a = 0（成对抵消）、a ^ 0 = a（0 当初始值）、交换律结合律（顺序无关）。
• 例 2（数 1 的个数）： 运算符 & 按位与；技巧 n & (n - 1) 消去最低位的一个 1；lowbit 思想；内置函数 __builtin_popcount 作对照。

2. 解题固定思考流程（审题模板）

题干出现"成对、去重、奇偶、2 的幂、二进制位数、取/设/翻转某一位、翻转取反、小数据状态压缩"这类词时，第一时间想位运算。位运算的价值在于——它能把"成对抵消""数 1"这种操作，用一行代码、O(1) 或极少次循环就完成，远胜于哈希表或字符串模拟。

拿到一道疑似能用位运算的题，按顺序过一遍：

1. 抓条件：题目给了什么数字、什么限制、什么"成对 / 奇偶 / 二进制"特征？

2. 定需求：我到底要求什么（去重？计数？判断？取位？）。

3. 匹配技巧：翻开「概念」里的"触发清单"，看题干信号命中哪一条 → 选对应的运算符 / 技巧。

4. 想对比：如果不用位运算（哈希表 / 排序 / 字符串模拟）会怎样？位运算是否更省空间 / 更短 / 更稳？

5. 落地写代码：先想清"初始值"（常用 0 或全 1 掩码），再写循环 / 判断，所有位运算条件都加括号。

3. 两道例题最容易漏的写代码细节（通用错误见「常见错误」）

下面三点是把例 1、例 2 真正写对时最常被忽略的地方；至于「优先级 / 移位溢出 / 负数移位 / & 当 && 用」这些通用错误，本文「常见错误」一节有逐条展开和例子，这里不再重复——写代码前务必去那里过一遍。

• ❌ 初始值设错：异或类题目初始值用 0（单位元 a ^ 0 = a）；计数类记得 cnt = 0 初始化，多组输入时要每组重新初始化。
• ❌ 多组输入忘了重置变量：while(cin>>n) 里 cnt、ans 每次都要归 0，否则会累加上一组的结果。
• ❌ n & (n-1) 用在 n = 0：要先保证 n > 0 再进循环（循环条件 n > 0 已经挡住了）；0 的二进制没有 1，本就直接返回 0。

写法总表

题面卡住时，用这张「技法分层」表定位你落在本能的哪一层（按粒度由细到粗）：

这六行按粒度由细到粗排：某一位 → 最低位的那个 1 → 整串的异或性质 → 整个当集合 → 逐位剥开。判断一道题落在哪一层，写法就定了，剩下的都是把 1 << k 这张掩码套上去。

三张表各管一段，别混：「概念 · 触发清单」管认题（题目出现什么词该想到位运算）；「定义 · 技巧速查表」管落笔（每个操作具体怎么写）；本表管归类（这道题落在哪种技法粒度）。从读题到写代码，依次查这三张即可。

只会手算 5 & 3 = 1 是不够的。位运算题考的是把一串 0 和 1 当成一排开关、或者当成一个集合去操作，手算只是最底下的一步。

常见错误

1. 优先级：<<、>> 高于 &、^、|；而 ==、<、> 又高于位运算。所以 if (a & 1 == 0) 是错的（先算 1 == 0），要写成 if ((a & 1) == 0)。位运算一律加括号。

2. 溢出：1 << 40 是 int 运算，直接溢出（结果未定义）。要写 1LL << 40。

3. 右移负数：在竞赛的 GCC（C++20 起标准规定为算术右移）里，负数右移高位补符号位，-4 >> 1 得 -2——这是确定行为，不是 0。但初学阶段仍建议位运算只用于非负整数，避免依赖这种细节。

4. 混淆 & 和 &&：3 & 5 = 1（按位与），3 && 5 = 1（逻辑真）。位运算写 &，条件判断写 &&。

5. 最高位别直接当正数用：(1 << 31) 在 int 里是负数，拿它做 > 0 判断会出错。涉及高位一律改用 long long。

6. 树状数组用了 0 下标：lowbit(0) = 0，循环 i += lowbit(i) 会死循环。下标从 1 开始。

自测

1. 写出把整数 n 的第 3 位（从 0 数起）置 1、清 0、取反的三个表达式。

2. n & (n - 1) 每做一次，n 里少了什么？用它怎么判断 n 是不是 2 的幂？lowbit(n) 又是剩下了什么？

3. 异或去重（例 1）为什么要求"成对"（偶数次）出现？如果某个数出现 3 次（奇数次）、且只有它落单，异或一遍的结果还等于它吗？说明原因。

4. 题目说 n ≤ 16，要求在 n 个元素里选若干个使某个值最大，第一时间应该想到哪种技术？枚举全部选法该写什么循环？

5. 1 << 40 和 1LL << 40 有什么区别？为什么前者是错的？

6. 树状数组里 lowbit(i) 同时扮演了哪两个角色？为什么它的单点加和前缀和查询都只要 O(log n)？

迁移练习

举一反三：迁移运用指南（拿到陌生题怎么想）

审题思考流水线（拿到陌生题，按顺序自问）：

① 题目要求求什么？（去重？计数？判断奇偶/幂？取某一位？状态枚举？）

② 数据范围多大，暴力能不能过？（n ≤ 20 往往暗示状态压缩；n 很大又要求 O(1) 空间往往暗示位运算技巧）

③ 有没有出现位运算对应的特征条件？（对照本文「概念」里的触发清单：成对/奇偶/二进制/取位/翻转/2 的幂）

④ 如果用上位运算，可以简化哪一部分计算？（是把"哈希统计"简化成"一行异或"？还是把"字符串数 1"简化成"几次 & 操作"？）

⑤ 需要搭配别的算法吗？（位运算常和枚举、贪心、DP 组合，比如"状态压缩 DP"就是用整数的一位表示一个物品选不选）

把这条流水线养成习惯：每次看到上述信号，先问自己①②③，再决定上不上位运算。

练手题（只给题干，先自己判断能不能用位运算、该用哪一条）

题干片段 A（01 字符串）：

给定两个长度均为 n 的 01 字符串 s 和 t。每次操作你可以把 s 中的某一个字符由 0 翻成 1 或 1 翻成 0。问：最少需要操作几次，才能让 s 变得和 t 完全相同？ （提示：先想两个字符串在哪些位置"不一样"；"不一样"这个动作，和哪个位运算符的逐位规则一致？）

题干片段 B（01 矩阵）：

有一个 n×n 的 01 矩阵。每次操作你可以选择某一行或某一列，把这一行/列的所有数字全部取反（0 变 1，1 变 0）。给定目标矩阵，问能否通过若干次操作，从全 0 矩阵变成目标矩阵？ （提示：注意"取反"二字——哪个位运算符表示"不同才变、相同不变"？行和列的多次取反，用异或来看会不会相互抵消？）

练习要求： 对上面两题，先别急着写代码，用本文的"触发清单"判断：① 题干出现了哪些位运算信号？② 应该优先考虑哪个运算符 / 技巧？③ 如果不用位运算，你会怎么暴力做？位运算能简化哪一步？想清楚这三点，再动手写，你就真正"会用了"。