位运算 Bit Manipulation
位运算 Bit Manipulation
位运算是处理二进制位的基本操作，在算法题中经常用于优化空间和时间复杂度。
基础操作 Basic Operations
按位与 AND (&)
- 两个位都为1时，结果为1
- 示例：
5 & 3 = 101 & 011 = 001 = 1 - 应用：清除特定位、判断奇偶性
按位或 OR (|)
- 至少一个位为1时，结果为1
- 示例：
5 | 3 = 101 | 011 = 111 = 7 - 应用：设置特定位、合并标志位
按位异或 XOR (^)
- 两个位不同时，结果为1
- 示例：
5 ^ 3 = 101 ^ 011 = 110 = 6 - 应用：查找单一元素、交换数字
按位取反 NOT (~)
- 0变1，1变0
- 示例：
~5 = ~(101) = 11111111111111111111111111111010（补码表示） - 应用：生成掩码、位的补集
移位操作 Shift
- 左移(<<)：
x << n相当于 x × 2ⁿ - 右移(>>)：
x >> n相当于 x ÷ 2ⁿ - 示例：
5 << 1 = 101 << 1 = 1010 = 10
常用技巧 Common Techniques
判断奇偶 Check Odd/Even
def isOdd(n: int) -> bool:
return n & 1 == 1获取最低位的1 Get Lowest Set Bit
def getLowestSetBit(n: int) -> int:
return n & -n清除最低位的1 Clear Lowest Set Bit
def clearLowestSetBit(n: int) -> int:
return n & (n - 1)判断2的幂 Check Power of Two
def isPowerOfTwo(n: int) -> bool:
return n > 0 and (n & (n - 1)) == 0统计1的个数 Count Set Bits
def countSetBits(n: int) -> int:
count = 0
while n:
n &= (n - 1) # 清除最低位的1
count += 1
return count实际应用 Practical Applications
1. 状态压缩 State Compression
- 使用一个整数表示多个布尔状态
- 节省空间，操作高效
class Permissions:
def __init__(self):
self.flags = 0
def addPermission(self, permission: int):
self.flags |= (1 << permission)
def removePermission(self, permission: int):
self.flags &= ~(1 << permission)
def hasPermission(self, permission: int) -> bool:
return (self.flags & (1 << permission)) != 02. 位掩码 Bit Masking
- 用于提取或设置特定位
def getBits(n: int, start: int, length: int) -> int:
mask = (1 << length) - 1
return (n >> start) & mask3. 权限管理 Permission Management
- 使用位运算高效管理权限
READ = 4 # 100
WRITE = 2 # 010
EXECUTE = 1 # 001
def checkPermissions(userPerms: int, requiredPerms: int) -> bool:
return (userPerms & requiredPerms) == requiredPerms经典题目 Classic Problems
1. 只出现一次的数字 (136. Single Number)
def singleNumber(nums: List[int]) -> int:
result = 0
for num in nums:
result ^= num
return result2. 汉明距离 (461. Hamming Distance)
def hammingDistance(x: int, y: int) -> int:
return bin(x ^ y).count('1')3. 数字范围按位与 (201. Bitwise AND of Numbers Range)
def rangeBitwiseAnd(left: int, right: int) -> int:
shift = 0
while left != right:
left >>= 1
right >>= 1
shift += 1
return left << shift4. 颠倒二进制位 (190. Reverse Bits)
def reverseBits(n: int) -> int:
result = 0
for i in range(32):
result = (result << 1) | (n & 1)
n >>= 1
return result性能考虑 Performance Considerations
- 位运算通常比算术运算快
- 可以减少内存使用
- 适合处理标志位和状态
- 在底层系统编程中广泛使用
注意事项 Important Notes
- 注意有符号数和无符号数的区别
- 考虑整数溢出的情况
- 位运算的可读性较差，需要良好的注释
- 不同编程语言的位运算可能有细微差别
练习建议 Practice Suggestions
- 从基本操作开始，理解每个操作的本质
- 多画图理解位的变化
- 从简单题目开始，逐步增加难度
- 关注位运算在实际项目中的应用