位运算（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 常见用途

1. 判断奇偶数

bool isOdd = (x & 1);  // 最低位为1是奇数

2. 清除最低位的1

x = x & (x - 1);  // 常用于统计1的个数

3. 统计一个数的二进制中1的个数（Brian Kernighan 算法）

int count = 0;
while (x) {x &= (x - 1);++count;
}

4. 交换两个变量（不使用临时变量）

a ^= b;
b ^= a;
a ^= b;

5. 判断某一位是否为1

bool isSet = (x & (1 << k));  // 判断第 k 位是否为1

6. 设置/清除/翻转某一位

x |= (1 << k);     // 设置第k位为1
x &= ~(1 << k);    // 清除第k位
x ^= (1 << k);     // 翻转第k位

7. 将整数转换为2的倍数（高效乘以2、除以2）

x << 1  // 相当于 x * 2
x >> 1  // 相当于 x / 2

8. 判断是否为2的幂

bool isPowerOfTwo = (x > 0) && ((x & (x - 1)) == 0);

9. XOR 找不同元素（如只出现一次的数）

int result = 0;
for (int num : nums) {result ^= num;
}

10. 位掩码（Bitmask）处理状态组合

int state = 0;
state |= (1 << 2);    // 设置第2位表示某功能启用
bool enabled = state & (1 << 2);

11. 得到最低有效位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 原生命令，速度极快；
• 节省空间：可以用位表示多个布尔状态；
• 用于状态压缩与组合计算；
• 应用广泛：位图、哈希、图算法、压缩、图形、嵌入式、权限控制等。