位操作技巧
基础回顾
位运算符
| 运算符 | 说明 | 示例 |
|---|---|---|
& | 按位与 | 5 & 3 = 1 (0101 & 0011 = 0001) |
| ` | ` | 按位或 |
^ | 按位异或 | 5 ^ 3 = 6 (0101 ^ 0011 = 0110) |
~ | 按位取反 | ~5 = -6 |
<< | 左移 | 5 << 1 = 10 |
>> | 右移 | 5 >> 1 = 2 |
常用技巧
python
# 常用常量
pow(2, 16) # 65536
pow(2, 32) # 4294967296
pow(2, 64) # 18446744073709551616
# 2 的幂次判断
n & (n-1) == 0 # 判断 n 是否为 2 的幂
# 获取最低的 1 位
n & (-n) # 保留最低位的 1
# 清除最低的 1 位
n & (n-1) # 清除最低位的 1常用技巧
1. 判断奇偶
python
def is_even(n):
return (n & 1) == 0
def is_odd(n):
return (n & 1) == 1原理：
- 奇数的最低位是 1
- 偶数的最低位是 0
n & 1只保留最低位
2. 判断是否为 2 的幂
python
def is_power_of_two(n):
return n > 0 and (n & (n - 1)) == 0原理：
- 2 的幂：1000, 10000, 100000...
- n-1：0111, 01111, 011111...
n & (n-1)= 0
示例：
n = 8 (1000)
n-1 = 7 (0111)
8 & 7 = 0 ✓ 是2的幂
n = 6 (0110)
n-1 = 5 (0101)
6 & 5 = 4 (0100) ≠ 0 ✗ 不是2的幂3. 获取最低位的 1
python
def get_lowest_bit(n):
return n & (-n)原理：负数的补码表示
示例：
n = 12 (01100)
-n = -12 (补码: 10100)
12 & -12 = 4 (00100) ✓4. 清除最低位的 1
python
def clear_lowest_bit(n):
return n & (n - 1)应用：统计 1 的个数
python
def count_ones(n):
count = 0
while n:
n = n & (n - 1) # 清除最低位的 1
count += 1
return count原理：每次操作清除一个 1，直到 n 变为 0
5. 交换两个数（不使用临时变量）
python
def swap(a, b):
a = a ^ b
b = a ^ b # b = (a ^ b) ^ b = a
a = a ^ b # a = (a ^ b) ^ a = b
return a, b6. 判断两位是否相同
python
def are_bits_different(a, b):
return (a ^ b) == 0等价于 a == b
7. 找出缺失的数字
场景：0-n 中缺失一个数字
python
def find_missing(nums, n):
"""
XOR 所有数组元素和 0-n，如果缺少 k，
结果就是 k
"""
result = 0
for i, num in enumerate(nums):
result ^= num ^ (i + 1)
return result原理：
a ^ a = 0a ^ 0 = a- XOR 满足交换律和结合律
8. 找出出现奇数次的元素
场景：数组中除一个元素外，其他都出现偶数次
python
def find_odd_occurrence(nums):
result = 0
for num in nums:
result ^= num
return result9. 高效的乘法除法
python
# 乘以 2^n
n << k # 等价于 n * pow(2, k)
# 除以 2^n
n >> k # 等价于 n // pow(2, k)示例：
python
n * 8 = n << 3
n / 8 = n >> 3
n * 10 = (n << 3) + (n << 1) # 8n + 2n = 10n10. 位域压缩
python
def encode(r, g, b):
"""RGB 各 8 位压缩成一个 24 位整数"""
return (r << 16) | (g << 8) | b
def decode(color):
"""从 24 位整数中提取 RGB"""
r = (color >> 16) & 0xFF
g = (color >> 8) & 0xFF
b = color & 0xFF
return r, g, b实战模板
模板：位运算通用检查
python
def bit_operations_checklist():
"""
面试时快速检查的位操作技巧：
"""
# 1. 判断奇偶
is_even = (n & 1) == 0
# 2. 判断 2 的幂
is_power_of_two = n > 0 and (n & (n-1)) == 0
# 3. 获取最低位的 1
lowest_bit = n & (-n)
# 4. 清除最低位的 1
cleared = n & (n-1)
# 5. 统计 1 的个数
count = 0
while n:
n &= n - 1
count += 1常用位运算公式
| 操作 | 公式 |
|---|---|
| 判断奇偶 | n & 1 |
| 2 的幂判断 | n & (n-1) == 0 |
| 最低位的 1 | n & (-n) |
| 清除最低位的 1 | n & (n-1) |
| 统计 1 的个数 | while(n): n &= n-1; count++ |
| 判断第 k 位 | (n >> k) & 1 |
| 设置第 k 位 | n | (1 << k) |
| 清除第 k 位 | n & ~(1 << k) |
| 切换第 k 位 | n ^ (1 << k) |
注意事项
- 负数右移 - 算术右移，保留符号位
- 溢出 - 位运算不会溢出，但结果可能不符合预期
- 优先级 - 位运算优先级较低，记得加括号
python
# 常见错误
result = x & y == z # 错误！先比较 ==，再 &
result = x & (y == z) # 正确