位运算 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)) != 0

2. 位掩码 Bit Masking

  • 用于提取或设置特定位
def getBits(n: int, start: int, length: int) -> int:
    mask = (1 << length) - 1
    return (n >> start) & mask

3. 权限管理 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 result

2. 汉明距离 (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 << shift

4. 颠倒二进制位 (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

  1. 位运算通常比算术运算快
  2. 可以减少内存使用
  3. 适合处理标志位和状态
  4. 在底层系统编程中广泛使用

注意事项 Important Notes

  1. 注意有符号数和无符号数的区别
  2. 考虑整数溢出的情况
  3. 位运算的可读性较差,需要良好的注释
  4. 不同编程语言的位运算可能有细微差别

练习建议 Practice Suggestions

  1. 从基本操作开始,理解每个操作的本质
  2. 多画图理解位的变化
  3. 从简单题目开始,逐步增加难度
  4. 关注位运算在实际项目中的应用

参考资源 References

  1. LeetCode Bit Manipulation Tag
  2. Bit Twiddling Hacks
  3. 位运算的基础知识