GESP 5级
位运算 与/或/非/异或
5级 · 基础算法与数据类型
📖 什么是位运算？
我们平时用的 +、-、*、/ 是对数值进行运算。而位运算是直接对数字的二进制表示中的每一位（bit）进行运算。
打个比方：普通运算是"按计算器"，位运算则是"直接操作计算器里的电路开关"——更底层、更快、更巧妙。
C++ 提供四种基本位运算符：
& 按位与（AND） — 两位都为1才为1
| 按位或（OR） — 有一位为1就为1
^ 按位异或（XOR）— 不同为1，相同为0
~ 按位取反（NOT） — 0变1，1变0
| 按位或（OR） — 有一位为1就为1
^ 按位异或（XOR）— 不同为1，相同为0
~ 按位取反（NOT） — 0变1，1变0
🌟 为什么重要？
- 速度极快：位运算是 CPU 最原生的操作，比乘除法快很多，在竞赛中用来"卡时间"。
- 状态压缩：用一个整数的二进制位来表示集合的状态（比如"哪些物品被选中"），这就是"状态压缩 DP"的基础。
- 交换两个数：不用临时变量就能交换两个数（
a ^= b; b ^= a; a ^= b;），虽然面试炫技更多，但理解异或很重要。 - 判断奇偶：
x & 1可以瞬间判断一个数是奇数还是偶数，比x % 2更高效。 - 清零最低位：
x & (x-1)可以把 x 二进制中最右边的 1 变成 0，这是很多算法题的巧妙技巧。
📋 前置知识
- ✅ 了解二进制的表示方法（每个数可以用 0 和 1 的串来表示）
- ✅ 十进制和二进制的互相转换（参考"任意进制转换"页面）
- ✅ 基本的 C++ 语法（变量、输出、循环）
🔢 & 按位与（AND）
规则：两个位都为 1，结果才为 1；否则为 0。
生活类比：想象两个人投票，两个人都同意才通过——这就是"与"。
📐 运算规则
0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1
示例：12 & 10
12 的二进制：1 1 0 0
10 的二进制：1 0 1 0
─────────────────
& 运算结果：1 0 0 0 = 8
10 的二进制：1 0 1 0
─────────────────
& 运算结果：1 0 0 0 = 8
常见用途：x & 1 判断奇偶——如果结果是 1 就是奇数，0 就是偶数。因为只有最后一位是 1 时结果才为 1。
🔢 | 按位或（OR）
规则：两个位中至少有一个为 1，结果就为 1；全为 0 才是 0。
生活类比：两个人投票，只要有一个人同意就通过——这就是"或"。
📐 运算规则
0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 1
0 | 1 = 1
1 | 0 = 1
1 | 1 = 1
示例：12 | 10
12 的二进制：1 1 0 0
10 的二进制：1 0 1 0
─────────────────
| 运算结果：1 1 1 0 = 14
10 的二进制：1 0 1 0
─────────────────
| 运算结果：1 1 1 0 = 14
常见用途：x | (1 << k) 把 x 的第 k 位设为 1。比如要标记"第 3 个物品被选中"，就可以用或运算。
🔢 ^ 按位异或（XOR）
规则：两个位不同为 1，相同为 0。
生活类比：两个人意见不同时才算通过，意见相同时不通过——这就是"异或"。
📐 运算规则
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0
示例：12 ^ 10
12 的二进制：1 1 0 0
10 的二进制：1 0 1 0
─────────────────
^ 运算结果：0 1 1 0 = 6
10 的二进制：1 0 1 0
─────────────────
^ 运算结果：0 1 1 0 = 6
异或的神奇性质：
① x ^ x = 0（自己异或自己 = 0）
② x ^ 0 = x（异或 0 不变）
③ a ^ b = b ^ a（交换律）
④ (a ^ b) ^ c = a ^ (b ^ c)（结合律）
用性质①②可以找"只出现一次的数"：
把所有数异或起来，成对出现的都抵消了，只剩下那个唯一的数。
② x ^ 0 = x（异或 0 不变）
③ a ^ b = b ^ a（交换律）
④ (a ^ b) ^ c = a ^ (b ^ c)（结合律）
用性质①②可以找"只出现一次的数"：
把所有数异或起来，成对出现的都抵消了，只剩下那个唯一的数。
🔢 ~ 按位取反（NOT）
规则：把每一位翻转，0 变 1，1 变 0。
就像"拍照反色"一样——黑色变白色，白色变黑色。
注意：在 C++ 中，~0 的结果是 -1（因为负数用补码表示），初学者不需要深究补码，知道取反的逐位操作即可。
💻 综合代码示例
💻 完整演示
#include <iostream>
#include <bitset> // 用来把整数显示为二进制，方便观察
using namespace std;
int main() {
int a = 12; // 二进制: 1100
int b = 10; // 二进制: 1010
// 输出原始值和二进制表示
cout << "a = " << a << " (二进制: " << bitset<8>(a) << ")" << endl;
cout << "b = " << b << " (二进制: " << bitset<8>(b) << ")" << endl;
// 1. 按位与 &：两位都1才1
cout << "a & b = " << (a & b) << endl; // 输出: 8 (二进制: 1000)
// 2. 按位或 |：有一位1就1
cout << "a | b = " << (a | b) << endl; // 输出: 14 (二进制: 1110)
// 3. 按位异或 ^：不同为1，相同为0
cout << "a ^ b = " << (a ^ b) << endl; // 输出: 6 (二进制: 0110)
// 4. 按位取反 ~：0变1，1变0
cout << "~a = " << (~a) << endl; // 输出: -13
// ====== 常用技巧 ======
// 技巧1：判断奇偶
int x = 7;
if (x & 1) {
cout << x << " 是奇数" << endl; // 会执行这行
} else {
cout << x << " 是偶数" << endl;
}
// 技巧2：交换两个数（不需要临时变量）
int m = 5, n = 9;
cout << "交换前: m=" << m << ", n=" << n << endl;
m ^= n; // m = m ^ n
n ^= m; // n = n ^ (m ^ n) = n ^ n ^ m = m
m ^= n; // m = (m ^ n) ^ m = n
cout << "交换后: m=" << m << ", n=" << n << endl;
// 技巧3：找只出现一次的数
// 数组 [2, 3, 5, 3, 2] 中，5 只出现了一次
int arr[] = {2, 3, 5, 3, 2};
int result = 0;
for (int i = 0; i < 5; i++) {
result ^= arr[i]; // 全部异或，成对的抵消
}
cout << "只出现一次的数: " << result << endl; // 输出: 5
return 0;
}⚠️ 易错点
🚨 常见错误
- 位运算和逻辑运算搞混：
&是"按位与"（逐位操作），&&是"逻辑与"（只看真假）。3 & 1 = 1，而3 && 1 = 1——虽然结果一样，但含义完全不同。对于2 & 1 = 0但2 && 1 = 1，就完全不一样了。 - 运算符优先级：位运算的优先级比比较运算符低！
a & b == 0实际上是a & (b == 0)，要用括号：(a & b) == 0。 - 异或交换的写法顺序：三行必须按顺序写，顺序错了结果就不对：
m ^= n; n ^= m; m ^= n; - ~ 取反的结果：
~0不是 -1 的"绝对值取反"，而是二进制全 1，在 int 下是 -1。~1是 -2，不要被负数吓到。 - 不要滥用位运算：位运算虽然快，但可读性差。竞赛中用没问题，平时写代码还是优先用清晰的写法，除非性能真的不够。
📝 练习建议
💡 怎么练？
- 手写二进制验证：每次做位运算题，先在纸上写出两个数的二进制，逐位运算，再和程序对比。
- 背熟异或的性质：x^x=0、x^0=x 是解题的核心。很多"找唯一数"的题都靠这个。
- 练习"只出现一次的数"：LeetCode 136 是经典入门题，数组里其他数都出现两次，找那个只出现一次的。
- 练习状态压缩：用一个整数的二进制位表示集合，比如 5 = 101 表示"选了第0个和第2个物品"。
- 推荐题目：洛谷 P1461（二进制相关）、LeetCode 136/191/338。