位运算必刷8题：异或、计数与二进制技巧

引言

位运算题是面试中「性价比」最高的一类：知识点少（与、或、非、异或、移位），但技巧性极强。异或（XOR）三定律是半壁江山，剩下的靠「位计数」和「最低位 1 的操作」解决。

本文精选 8 道必刷位运算题，从异或入门到二进制技巧，每道题讲透「为什么能用位运算」，并汇总一张速查表。

前置：了解 & | ^ ~ << >> 五种运算符。数学类配合见 /leetcode-math-essential-problems/。

目录

• 1. 位运算基础速查
• 2. 只出现一次的数字（LeetCode 136）— XOR 去重
• 3. 位1的个数（LeetCode 191）— 位计数
• 4. 汉明距离（LeetCode 461）— XOR 后计数
• 5. 2 的幂（LeetCode 231）— 最低位技巧
• 6. 缺失的数字（LeetCode 268）— XOR 成对消除
• 7. 颠倒二进制位（LeetCode 190）— 逐位搬运
• 8. 数字范围按位与（LeetCode 201）— 公共前缀
• 9. 位运算实现加法（LeetCode 371）— 无进位加法
• 10. 位运算速查表
• 延伸阅读

1. 位运算基础速查

XOR 三大定律（位运算题的灵魂）：

1. 交换律/结合律：a ^ b ^ c == c ^ b ^ a
2. 自身异或为零：a ^ a == 0
3. 与 0 异或不变：a ^ 0 == a

推论：一堆数里「只有一个是奇数次，其余都是偶数次」，全部异或起来就得到那个奇数次的数。

2. 只出现一次的数字（LeetCode 136）— XOR 去重

问题：数组中只有一个数出现一次，其余都出现两次，找出它。

思路：全部异或。成对的数异或为 0，0 异或唯一数 = 它本身。

def single_number(nums):
    result = 0
    for num in nums:
        result ^= num
    return result

时间复杂度 O(n)，空间 O(1)——这是异或不可替代的优势（HashMap 需要 O(n) 空间）。

变体：只出现一次的数字 III（260） — 两个唯一数 → 先全部异或得到 a ^ b，取最低位的 1 分组再异或。见速查表。

3. 位1的个数（LeetCode 191）— 位计数

问题：统计无符号整数二进制表示中 1 的个数。

方法一（最低位消除）：x = x & (x - 1) 每次消掉最低位的 1，循环次数 = 1 的个数。

def hamming_weight(n):
    count = 0
    while n:
        n &= n - 1      # 消掉最低位的 1
        count += 1
    return count

为什么 x & (x-1) 能消最低位 1：x-1 会把最低位 1 变成 0，并把其后的 0 全变 1；x & (x-1) 就把最低位 1 及其后位全部清掉，高位不变。

4. 汉明距离（LeetCode 461）— XOR 后计数

问题：两个整数二进制表示中对应位不同的个数。

思路：x ^ y 中 1 的个数就是不同位的个数 → 复用位计数。

def hamming_distance(x, y):
    xor = x ^ y
    count = 0
    while xor:
        xor &= xor - 1
        count += 1
    return count

联系：汉明距离 → 汉明重量（位1个数）→ 位计数。一脉相承。

5. 2 的幂（LeetCode 231）— 最低位技巧

问题：判断整数 n 是否为 2 的幂。

思路：2 的幂二进制只有一位 1 → n & (n - 1) == 0。

def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0

注意 n > 0：0 和负数也要排除。

变体：4 的幂（342） — 在 2 的幂基础上再要求 n % 3 == 1（数学性质）。3 的幂（326） — 直接 n % 3 == 1 配合循环。

6. 缺失的数字（LeetCode 268）— XOR 成对消除

问题：0..n 中缺了一个数，数组长度为 n，找出缺失的。

思路：把下标和值全部异或——每个「下标 == 值」的数成对出现被消除，剩下的就是缺失值。

def missing_number(nums):
    result = 0
    for i, num in enumerate(nums):
        result ^= i ^ num
    result ^= len(nums)      # 把 n 也加入
    return result

为什么对：完整集合是 {0,1,...,n}，出现集合是 {0,1,...,n} \ {missing}。两者异或 = 缺失值（因为其他数都成对出现）。

7. 颠倒二进制位（LeetCode 190）— 逐位搬运

问题：将 32 位无符号整数二进制位颠倒（如 43261596 → 964176192）。

思路：从低位到高位逐位取出，放到结果的对应高位。用 << 和 | 拼接。

def reverse_bits(n):
    result = 0
    for i in range(32):
        result = (result << 1) | (n & 1)   # 左移腾位 + 取当前最低位
        n >>= 1
    return result

要点：Python 的 >> 对无符号数需保证 32 位内运算，结果仍视为 32 位无符号（用 result & 0xFFFFFFFF 保险）。

8. 数字范围按位与（LeetCode 201）— 公共前缀

问题：求 [m, n] 范围内所有整数按位与的结果。

核心观察：范围按位与的结果 = m 和 n 的公共前缀（后面补 0）。因为一旦某一位在某次进位中变 0，之后就一直是 0。

def range_bitwise_and(m, n):
    shift = 0
    while m < n:
        m >>= 1
        n >>= 1
        shift += 1
    return m << shift

示例：[5,7] → 5(101), 6(110), 7(111) → 按位与 = 100 = 4 = 公共前缀 10 + 0。右移直到 m==n，再左移回来。

9. 位运算实现加法（LeetCode 371）— 无进位加法

问题：不用 +、- 实现两整数相加。

思路：a ^ b 得到无进位和，(a & b) << 1 得到进位，循环直到进位为 0。

def get_sum(a, b):
    while b:
        carry = (a & b) << 1     # 进位
        a ^= b                   # 无进位和
        b = carry
    return a

注意：Python 整数无限长，负数需用 & 0xFFFFFFFF 处理补码，否则会死循环（负数右移补 1 永不消 0）。

def get_sum_safe(a, b):
    mask = 0xFFFFFFFF
    while b & mask:
        carry = (a & b) << 1
        a = (a ^ b) & mask
        b = carry
    return a if a <= 0x7FFFFFFF else ~(a ^ mask)   # 处理符号

10. 位运算速查表

记忆口诀：XOR 成对消，x&(x-1) 数一，n&(n-1)==0 判单 1，位题一网打尽。

延伸阅读

• /leetcode-math-essential-problems/ — 数学题与位运算配合
• /leetcode-backtracking-problems/ — 位运算也常用于子集枚举（状态压缩）
• LeetCode 位运算标签 — 完整题库