⚡ 位运算 — 二进制的微观世界

📖 位运算的核心概念

位运算是直接操作二进制位的技巧，可以将某些操作从 O(n) 优化到 O(1) 或 O(log n)。面试中常考：位计数、位掩码、异或技巧。理解位运算的关键是把数字看作二进制串。

1. 位运算常见技巧

2. Python 位运算注意事项

# Python 整数无限精度，注意负数右移
-1 >> 1  # → -1 (算术右移，高位补1)

# 获取32位无符号值
n & 0xFFFFFFFF

# 二进制表示
bin(10)  # → '0b1010'
format(10, '032b')  # → '00000000000000000000000000001010'

# 位计数
bin(10).count('1')  # → 2 (但面试不能直接用)

🎯 题目一：位1的个数 (LC 191)

题目描述：给定一个无符号整数，返回其二进制表达式中1的个数（也称作汉明权重）。

思路分析

代码实现

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            n &= n - 1  # 清除最低位的1
            count += 1
        return count

复杂度分析

时间复杂度：O(k)，k 为 1 的个数（最多32）

空间复杂度：O(1)

🎯 题目二：比特位计数 (LC 338)

题目描述：给定整数 n，对于 0 ≤ i ≤ n 的每个 i，计算其二进制中1的个数，返回数组。

思路分析

代码实现

class Solution:
    def countBits(self, n: int) -> List[int]:
        dp = [0] * (n + 1)
        for i in range(1, n + 1):
            dp[i] = dp[i >> 1] + (i & 1)
        return dp

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

🎯 题目三：汉明距离 (LC 461)

题目描述：两个整数之间的汉明距离是这两个数对应二进制位不同的位置数目。

思路分析

代码实现

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        xor = x ^ y
        count = 0
        while xor:
            xor &= xor - 1
            count += 1
        return count

复杂度分析

时间复杂度：O(k)，k 为汉明距离

空间复杂度：O(1)

🔬 位运算高级技巧

1. 判断2的幂

# 2的幂只有一个1
def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0

# 原理: 8 = 1000, 7 = 0111
# 8 & 7 = 0 → 2的幂
# 6 = 0110, 5 = 0101
# 6 & 5 = 0100 ≠ 0 → 不是2的幂

2. 交换两个数（不用临时变量）

a ^= b
b ^= a
a ^= b
# 原理: a^b^b = a, a^b^a = b
# 面试炫技用，实际代码别这么写（可读性差）

3. 位掩码枚举子集

# 枚举集合 {0,1,...,n-1} 的所有子集
n = 3
for mask in range(1 << n):
    subset = [i for i in range(n) if mask & (1 << i)]
    print(f"mask={mask:03b}, subset={subset}")

# 输出:
# mask=000, subset=[]
# mask=001, subset=[0]
# mask=010, subset=[1]
# mask=011, subset=[0,1]
# mask=100, subset=[2]
# mask=101, subset=[0,2]
# mask=110, subset=[1,2]
# mask=111, subset=[0,1,2]

4. 只出现一次的数字

# LC 136: 数组中只有一个数出现一次，其余出现两次
def single_number(nums):
    result = 0
    for num in nums:
        result ^= num
    return result

# 原理: a^a=0, 所有成对的数异或抵消
# 剩下的就是只出现一次的数

📝 课后练习

1. LC 136 只出现一次的数字（异或抵消）
2. LC 137 只出现一次的数字 II（位计数）
3. LC 477 汉明距离总和（逐位统计）
4. LC 201 数字范围按位与（找公共前缀）
5. LC 421 数组中两个数的最大异或值（位+Trie）

🔑 本课要点回顾

• n & (n-1)：清除最低位的1，用于计数、判断2的幂
• n & (-n)：获取最低位的1，用于树状数组
• LC 338 DP：dp[i] = dp[i>>1] + (i&1)，利用二进制关系
• 汉明距离 = popcount(x ^ y)，异或后计数1
• 位掩码枚举子集是状态压缩DP的基础

📚 扩展阅读

• 《算法导论》位运算在算法中的应用
• 状态压缩 DP（旅行商问题 TSP）
• 树状数组（Binary Indexed Tree）中的 lowbit 操作
• LC 421 的 01-Trie 解法