位运算 Bit Manipulation

2026-06-02

面试出现率不高，但一旦出现完全靠记忆。背下来就是送分题。

5 个必会操作

操作 含义
n & 1 取最低位（判断奇偶）
n >> 1 右移一位（除以 2）
n & (n-1) 清掉最低位的 1
n & -n 取出最低位的 1（lowbit）
n ^ n == 0 相同的数异或为 0

异或 XOR 三大性质

  • a ^ 0 = a — 任何数异或 0 等于自身
  • a ^ a = 0 — 任何数异或自身等于 0
  • 可交换、可结合 — 顺序无关，可以随意分组

这三个性质组合起来：一堆数异或，成对的全消掉，落单的留下来。

6 个必背 Trick

1. 判断 2 的幂

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

2 的幂只有一个 1，n&(n-1) 清掉后变 0。

2. Popcount（数 1 的个数）

1
2
3
4
5
6
def popcount(n):
    count = 0
    while n:
        n &= n - 1  # 每次清掉一个 1
        count += 1
    return count

3. 枚举子集（bitmask）

1
2
3
4
# 枚举 n 个元素的所有子集
for mask in range(1 << n):
    # mask 的二进制表示哪些元素被选中
    pass

4. 枚举子集的子集

1
2
3
4
5
# 枚举 mask 的所有非空子集
sub = mask
while sub:
    # 处理 sub
    sub = (sub - 1) & mask

减 1 后与 mask 取 AND，自动跳到下一个合法子集。

5. 交换两数（仅 trivia，面试别用）

1
2
3
a ^= b
b ^= a
a ^= b

6. 找两个只出现一次的数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def singleNumbers(nums):
    xor_all = 0
    for x in nums:
        xor_all ^= x  # xor_all = a ^ b

    lowbit = xor_all & (-xor_all)  # 取最低位的 1

    a, b = 0, 0
    for x in nums:
        if x & lowbit:
            a ^= x
        else:
            b ^= x
    return a, b

lowbit 位上，a 和 b 一定不同（否则异或该位不会是 1），所以可以分组。

状态压缩 DP 模板（n<=20）

用一个整数 mask 表示集合的选取状态，第 i 位为 1 代表第 i 个元素已选。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 经典模板：TSP / 划分子集
n = len(nums)
dp = [float('inf')] * (1 << n)
dp[0] = 0  # 空集

for mask in range(1 << n):
    # 枚举下一个要加入的元素
    for i in range(n):
        if mask & (1 << i):
            continue  # 已经选过
        new_mask = mask | (1 << i)
        dp[new_mask] = min(dp[new_mask], dp[mask] + cost(mask, i))

# 或者枚举子集转移
for mask in range(1 << n):
    sub = mask
    while sub:
        dp[mask] = min(dp[mask], dp[mask ^ sub] + f(sub))
        sub = (sub - 1) & mask

时间复杂度 O(2^n * n) 或 O(3^n)，所以 n 一般不超过 20。

动画：位操作可视化

以 n = 13（二进制 1101）为例，对照动画看两件事：n & (n-1) 把最低位的 1 整个清掉，n & -n 只留最低位的 1。看完再回头读上面的 6 个 trick，肌肉记忆就建立了。

思考题

为什么 n&(n-1) 能清掉最低位的 1？从二进制角度解释。

n 的最低位的 1，假设在第 k 位。那么 n 的第 0~k-1 位全是 0，第 k 位是 1。

n-1 做的事情：第 k 位变 0，第 0~k-1 位全变 1（借位）。

所以 n & (n-1)：第 k 位 1&0=0（清掉了！），第 0~k-1 位 0&1=0，高位不变。

状态压缩 DP 为什么只适用于 n<=20？

状态数是 2^n。n=20 时有 100 万个状态，勉强能跑。n=25 就是 3300 万，n=30 就是 10 亿，内存和时间都扛不住。实际面试中一般 n<=16 比较常见，n=20 是极限。

"找两个只出现一次的数"中，为什么 lowbit 能把两个数分到不同组？

xor_all = a ^ b。lowbit 取出的是 a 和 b 第一个不同的位。在这一位上，a 是 1、b 是 0（或反过来）。按这一位分组，a 和 b 一定在不同组。其他成对的数，同一个数在同一组，异或后消掉。

LeetCode 题目

热身：136. Single Number、191. Number of 1 Bits、338. Counting Bits。

进阶：137. Single Number II、260. Single Number III、421. Maximum XOR、847. Shortest Path Visiting All Nodes、698. Partition to K Equal Sum Subsets。