位运算 (Bit Manipulation)

LeetCodeBit Manipulation位运算算法

位运算（Bit Manipulation）

位运算是直接对整数的二进制位进行操作的算法技巧，常用于状态压缩、集合枚举、快速计算等。

原理与常见操作

  • 与（&）、或（|）、异或（^）、取反（~）、左移（<<）、右移（>>）
  • 利用位运算实现加法、判断奇偶、交换数、统计1的个数等

典型例题

1. 只出现一次的数字

def singleNumber(nums):
    res = 0
    for num in nums:
        res ^= num
    return res

2. 汉明重量

def hammingWeight(n):
    count = 0
    while n:
        n &= n - 1
        count += 1
    return count

3. 颠倒二进制位

def reverseBits(n):
    res = 0
    for _ in range(32):
        res = (res << 1) | (n & 1)
        n >>= 1
    return res

应用场景

  • 状态压缩DP、子集枚举
  • 位图、权限控制、哈希
  • 快速判断奇偶、交换、计数

相关文章