位运算（Bitwise Operation）是直接对整数的二进制位进行操作的运算方式，在底层开发、性能优化、算法设计中广泛使用。
1 基本位运算符及含义
| 运算符 | 名称 | 示例（a=5, b=3） | 运算过程（二进制） | 结果 |
|---|---|---|---|---|
& |
按位与 | a & b = 1 |
0101 & 0011 = 0001 |
1 |
| |
按位或 | a | b = 7 |
0101 | 0011 = 0111 |
7 |
^ |
按位异或 | a ^ b = 6 |
0101 ^ 0011 = 0110 |
6 |
~ |
按位取反 | ~a = -6 |
~0101 = 1010（补码） |
-6 |
<< |
左移 | a << 1 = 10 |
0101 << 1 = 1010 |
10 |
>> |
右移 | a >> 1 = 2 |
0101 >> 1 = 0010 |
2 |
2 常见用途
- 判断奇偶数
bool isOdd = (x & 1); // 最低位为1是奇数
- 清除最低位的1
x = x & (x - 1); // 常用于统计1的个数
- 统计一个数的二进制中1的个数（Brian Kernighan 算法）
int count = 0;
while (x) {
x &= (x - 1);
++count;
}
- 交换两个变量（不使用临时变量）
a ^= b;
b ^= a;
a ^= b;
- 判断某一位是否为1
bool isSet = (x & (1 << k)); // 判断第 k 位是否为1
- 设置/清除/翻转某一位
x |= (1 << k); // 设置第k位为1
x &= ~(1 << k); // 清除第k位
x ^= (1 << k); // 翻转第k位
- 将整数转换为2的倍数（高效乘以2、除以2）
x << 1 // 相当于 x * 2
x >> 1 // 相当于 x / 2
- 判断是否为2的幂
bool isPowerOfTwo = (x > 0) && ((x & (x - 1)) == 0);
- XOR 找不同元素（如只出现一次的数）
int result = 0;
for (int num : nums) {
result ^= num;
}
- 位掩码（Bitmask）处理状态组合
int state = 0;
state |= (1 << 2); // 设置第2位表示某功能启用
bool enabled = state & (1 << 2);
- 得到最低有效位1
unsigned a = 12; // 1100
unsigned t = a & (-a); // 0b1100 & 0b0100 = 0b100
3 扩展技巧
- 最大/最小值幂（向上取最近2的幂）
unsigned int nextPowerOfTwo(unsigned int x) {
if (x == 0) return 1;
--x;
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
return x + 1;
}
- 子集枚举
for (int subset = mask; subset; subset = (subset - 1) & mask) {
// 枚举 mask 的所有子集
}
4 位运算的优势
- 高性能：CPU 原生命令，速度极快；
- 节省空间：可以用位表示多个布尔状态；
- 用于状态压缩与组合计算；
- 应用广泛：位图、哈希、图算法、压缩、图形、嵌入式、权限控制等。