位运算核心原理与高效算法实战

1. 位运算基础与核心概念

计算机底层处理数据的最小单位是二进制位，而位运算就是直接对整数在内存中的二进制位进行操作的技术。相比加减乘除等算术运算，位运算通常具有更高的执行效率，在算法优化、底层系统开发、嵌入式编程等领域有着广泛应用。

1.1 基本位运算符

现代编程语言普遍支持的6种基本位运算符：

1. 按位与(&)：对应位都为1时结果为1，否则为0

   python复制0b1100 & 0b1010 = 0b1000  # 十进制 12 & 10 = 8
   

2. 按位或(|)：对应位有1时结果为1，全0时为0

   python复制0b1100 | 0b1010 = 0b1110  # 12 | 10 = 14
   

3. 按位异或(^)：对应位不同时结果为1，相同时为0

   python复制0b1100 ^ 0b1010 = 0b0110  # 12 ^ 10 = 6
   

4. 按位取反(~)：所有位取反（注意补码表示）

   python复制~0b1100 = -0b1101  # ~12 = -13 (Python使用补码表示)
   

5. 左移(<<)：所有位向左移动，低位补0

   python复制0b1100 << 2 = 0b110000  # 12 << 2 = 48
   

6. 右移(>>)：所有位向右移动（有符号右移）

   python复制0b1100 >> 2 = 0b0011  # 12 >> 2 = 3
   

注意：不同语言对右移的处理可能不同。C/C++中负数右移补1（算术右移），Java/Python中保持符号位（逻辑右移）。

1.2 位运算的优先级陷阱

位运算符的优先级常常是代码错误的来源。以下是一个典型优先级顺序（从高到低）：

code复制~ > << >> > & > ^ > |

常见错误示例：

python复制# 错误：先计算 1|0 再左移
result = 1 << 1 | 0  # 实际等于 (1<<1)|0 = 2

# 正确：使用括号明确优先级
result = 1 << (1 | 0)  # 1<<1 = 2

1.3 位运算的实用性质

掌握这些性质可以大幅提升编码效率：

1. 异或的特殊性质：

   • 任何数与自己异或结果为0：x ^ x = 0
   • 异或满足交换律和结合律：a ^ b ^ a = b
   • 与0异或保持不变：x ^ 0 = x

2. 位移与乘除的关系：

   • 左移n位相当于乘以2ⁿ：x << n = x * 2ⁿ
   • 右移n位相当于除以2ⁿ取整：x >> n = x // 2ⁿ

3. 掩码操作：