位运算是一种基于二进制位的操作技术，广泛应用于算法优化、底层开发、压缩、加密等领域。位运算直接操作数据的二进制表示，因此效率极高。
目录
1. 位运算的基本操作
位运算包括以下几种基本操作：
(1) 按位与 (&)
定义：对两个二进制数的每一位进行比较，如果两个对应的位都为
1，则结果为1，否则为0。用途：
提取特定位：例如
x & 1可以判断x的最低位是否为1。
清零特定位：例如
x & ~(1 << n)可以将x的第n位清零。
示例：
int a = 5; // 0101 int b = 3; // 0011 int c = a & b; // 0001 (1)
(2) 按位或 (|)
定义：对两个二进制数的每一位进行比较，如果两个对应的位中至少有一个为
1，则结果为1，否则为0。用途：
设置特定位：例如
x | (1 << n)可以将x的第n位设置为1。
示例：
int a = 5; // 0101 int b = 3; // 0011 int c = a | b; // 0111 (7)
(3) 按位异或 (^)
定义：对两个二进制数的每一位进行比较，如果两个对应的位不同，则结果为
1，否则为0。
用途：
交换两个数：
a ^= b; b ^= a; a ^= b;。找唯一不重复的数：在一组数中，只有一个数出现一次，其他数出现两次，可以用异或找到。
示例：
int a = 5; // 0101 int b = 3; // 0011 int c = a ^ b; // 0110 (6)
(4) 按位取反 (~)
定义：对一个二进制数的每一位取反，
0变1，1变0。用途：
配合其他位运算使用，例如清零特定位。
示例：
int a = 5; // 0101 int b = ~a; // 1010 (补码表示，实际值为 -6)
(5) 左移 (<<)
定义：将一个二进制数的所有位向左移动若干位，右侧补
0。用途：
快速计算
2的幂：1 << n等价于2^n。构造掩码：例如
(1 << n) - 1可以生成n个1。
示例：
int a = 5; // 0101 int b = a << 1; // 1010 (10)
(6) 右移 (>>)
定义：将一个二进制数的所有位向右移动若干位，左侧补
0（逻辑右移）或符号位（算术右移）。用途：
快速除以
2：x >> 1等价于x / 2。提取高位：例如
x >> n可以提取x的高n位。
示例：
int a = 5; // 0101 int b = a >> 1; // 0010 (2)
上面的运算其实也属于位图的思想一部分：
2. 位运算的常见算法
以下是位运算在算法中的典型应用。
(1) 判断奇偶性
原理：一个数的二进制表示中，最低位为
1则是奇数，否则为偶数。异或运算也可以：
代码：
bool isOdd(int x) { return x & 1; }
(2) 交换两个数
原理：利用异或运算的性质
a ^ b ^ b = a。代码：
void swap(int &a, int &b) { a ^= b; b ^= a; a ^= b; }
(3) 统计二进制中 1 的个数
原理：利用
x & (x - 1)可以消除x的最后一个1。也可以提取最后一个1：
代码：
int countOnes(int x) { int count = 0; while (x) { x &= (x - 1); count++; } return count; }
(4) 判断一个数是否是 2 的幂
原理：
2的幂的二进制表示中只有一个1。代码：
bool isPowerOfTwo(int x) { return x > 0 && (x & (x - 1)) == 0; }
(5) 找唯一不重复的数
问题：一个数组中只有一个数出现一次，其他数出现两次，找出这个数。
原理：利用异或运算的性质
a ^ a = 0和a ^ 0 = a。代码：
int singleNumber(vector<int>& nums) { int result = 0; for (int num : nums) { result ^= num; } return result; }
3.关于二进制加法与位运算
重点扩展：
异或 (XOR) 和与 (AND) 的运算结果与二进制加法中的“和”与“进位”密切相关。 让我们用真值表来解释：
二进制加法:
| A | B | A + B | 和 (Sum) | 进位 (Carry) |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 10 | 0 | 1 |
异或 (XOR):
| A | B | A XOR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
与 (AND):
| A | B | A AND B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
比较:
观察到：
异或 (XOR) 的结果与二进制加法的“和”列完全相同。 它只关心两个输入位是否不同，如果不同则结果为 1（无进位）。
与 (AND) 的结果与二进制加法的“进位”列完全相同。 它只关心两个输入位是否都为 1，如果是则结果为 1（表示有进位）。
因此，我们可以说： A + B = (A XOR B) + 2*(A AND B) (其中 “+” 代表二进制加法，"2*" 代表左移一位，相当于乘以2)。 这表明二进制加法可以分解为异或运算（求和）和与运算（求进位）的组合。 异或运算得到“无进位加法”的结果，与运算得到“进位”的结果。
简单来说，异或关注的是“不同”，与关注的是“同时为真”。 在二进制加法的语境下，这分别对应“和”与“进位”。
4. 位运算的高级应用
(1) 状态压缩
原理：利用二进制位表示状态，常用于动态规划、回溯等算法中。
示例：
n个物品的选或不选可以用一个n位二进制数表示。int mask = 0; // 初始状态 mask |= (1 << i); // 选择第 i 个物品 bool isSelected = mask & (1 << i); // 判断第 i 个物品是否被选择
(2) 快速幂算法
原理：利用二进制分解指数，快速计算幂。
代码：
long long fastPow(int base, int exponent) { long long result = 1; while (exponent > 0) { if (exponent & 1) { result *= base; } base *= base; exponent >>= 1; } return result; }
5. 注意事项
符号位：右移操作时，有符号数和无符号数的行为不同。
溢出：左移可能导致溢出，尤其是对负数左移。
可读性：位运算虽然高效，但可读性较差，建议添加注释。