从算法到人工智能 · 第 5 课：位运算——计算机的"底层语言"

上一课我们玩的是指针——两个指针一快一慢，就把链表的问题拆得干干净净。这一课我们往更底层钻一层：直接跟计算机的"母语"打交道，也就是位（bit）。

你可能会嘀咕：我都用 Python 了，还要懂位运算干嘛？——好问题。但事实是，位运算在很多地方是绕不开的快车道：判断一个数是不是 2 的幂、在 O(1) 空间里找一个只出现一次的数、用一个整数优雅地表示"哪些开关被打开了"……这些题，不懂位运算，你写得又慢又啰嗦；懂了，一行搞定。

这一课的目标很简单：让你从"看见 & | ^ 就头皮发麻"，变成"这玩意真香"。

一、先补一个底：二进制是怎么回事

我们平时数数用的是十进制——逢十进一，每一位是 0~9。计算机里只有两种状态（通电/断电），所以它用的是二进制——逢二进一，每一位只有 0 和 1。

看一个十进制数 13，它怎么变成二进制：

13 = 8 + 4 + 1
   = 1×2³ + 1×2² + 0×2¹ + 1×2⁰
   = 1101 (二进制)

从右往左，每一位的"权重"是 1、2、4、8、16……（也就是 2⁰、2¹、2²、2³……）。所以 1101 从左到右是：

  1      1      0      1
 2³     2²     2¹     2⁰
  8      4      2      1

把有 1 的位加起来：8 + 4 + 1 = 13。搞懂了。

术语先说清楚：二进制的一位叫 bit（位）；8 个位叫一个 byte（字节）。Python 里 bin(13) 会打印 0b1101，0b 前缀表示"这是二进制"。

在 Python 里验证一下：

print(bin(13))          # 0b1101
print(int('1101', 2))   # 13  （把字符串当二进制转回十进制）

二、六种位运算符，一次讲透

位运算的本质是：把两个数按二进制逐位对齐，每一位单独做运算。一共六个运算符：

先看前三个（与、或、异或），把 13 和 10 对齐：

13  = 1101
10  = 1010
      ----
&     = 1000   (两位都是1的位置，只有最左边)
|     = 1111   (只要某位有1就保留)
^     = 0111   (两位不同的位置)

& 像"要两个人都点头"；| 像"只要有一个人点头"；^ 像"两个人意见不一致时记下来"。

再看三个单数运算符：

print(13 << 1)   # 26   （1101 → 11010，往左挪一位，末尾补0）
print(13 << 2)   # 52   （1101 → 110100）
print(13 >> 1)   # 6    （1101 → 110，往右挪一位，丢掉最右的1）

关键直觉（这个必须记住，太常用了）：

• 左移 1 位 = 乘以 2（x << 1 == x * 2）
• 右移 1 位 = 除以 2 取整（x >> 1 == x // 2）

因为二进制往左挪一位，每一位的权重都翻倍了，整体就乘 2。这个直觉能帮你秒懂后面所有技巧。

取反 ~ 稍微特殊一点（涉及 Python 的"补码"），我们这节课先不碰它，避免绕晕——90% 的算法题用 &、|、^、<<、>> 就够。

三、四大经典技巧：从"判断奇偶"到"数 1"

技巧 1：判断一个数是奇数还是偶数

奇数的二进制，最后一位一定是 1；偶数的最后一位一定是 0。所以拿它和 1 做与运算就行：

def is_odd(n):
    return n & 1 == 1

print(is_odd(7))   # True   (7 = 111，末位1)
print(is_odd(8))   # False  (8 = 1000，末位0)

原理：n & 1 会保留 n 的最后一位，其它位全清零。末位是 1 → 奇数；是 0 → 偶数。比 n % 2 == 1 更快（虽然 Python 里差别不明显，但这是位运算最经典的入门动作）。

技巧 2：不用临时变量，交换两个数

这个技巧曾经是面试"炫技"题，现在更多是帮助你理解异或的性质：

a, b = 5, 9
a = a ^ b
b = a ^ b   # 此时 b 变成了原来的 a
a = a ^ b   # 此时 a 变成了原来的 b
print(a, b)  # 9 5

为什么能行？因为异或有三个性质（下面会重点展开）：

1. x ^ x = 0（自己异或自己，全抵消）
2. x ^ 0 = x（异或 0 不变）
3. 交换律：a ^ b = b ^ a

你可以拿笔按上面三步走一遍，会发现 a、b 神奇地互换了。理解它比背它重要——这三条性质是下一节"找唯一数"的钥匙。

技巧 3：判断一个数是不是 2 的幂

2 的幂长这样：1, 2, 4, 8, 16, ...，二进制分别是 1, 10, 100, 1000, 10000, ...——有且只有一个 1。

巧妙的判断：n & (n - 1)。拿 8 和 7 看：

8     = 1000
7     = 0111
8 & 7 = 0000   → 结果是 0

规律：2 的幂减 1 后，恰好是"这一位变 0、后面全变 1"，两者做与运算，1 全部错开，结果为 0。而普通数（比如 6）就不行：

6     = 110
5     = 101
6 & 5 = 100   → 结果不是 0

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

print(is_power_of_two(16))  # True
print(is_power_of_two(6))   # False

技巧 4：统计二进制里有多少个 1

这是面试超高频题，也是技巧 3 的延伸。思路：每次用 n & (n-1) 消掉最低位的那个 1，循环计数：

def count_ones(n):
    count = 0
    while n:
        n = n & (n - 1)   # 每次消掉最低位的一个 1
        count += 1
    return count

print(count_ones(13))   # 3   (13 = 1101，有3个1)

为什么 n & (n-1) 正好消掉"最低位的 1"？看 13：

13     = 1101
12     = 1100
13&12  = 1100   → 最低位的那个 1（末位）被消掉了

再消一次：1100 & 1011 = 1000，又消掉一个。循环 3 次归零，正好数了 3 个 1。这个操作叫 "消最低位 1"（clear lowest set bit），是位运算里最重要的一个动作，务必刻进肌肉记忆。

四、位掩码：用一个整数表示"一堆开关"

位掩码（bitmask） 是位运算最优雅的应用：把整数当成"一排开关"，每一位代表一个东西的"开/关"状态。

想象你要管理一个用户有哪些权限：读、写、执行、删除。不用开四个布尔变量，只要一个整数，用四个位：

读(1)  写(2)  执行(4)  删除(8)   ← 每一类的"权重"是 1,2,4,8
 0      0       0       0

• 打开某个权限：用 |（或），因为 x | 1 = 1
• 关闭某个权限：用 & ~（与 + 取反）
• 检查是否有某个权限：用 &，结果非 0 就代表"有"

READ, WRITE, EXEC, DELETE = 1, 2, 4, 8

perm = 0                     # 一开始啥权限都没有
perm = perm | READ           # 打开读：perm = 1
perm = perm | WRITE          # 打开写：perm = 3  (1|2)
perm = perm | EXEC           # 打开执行：perm = 7 (1|2|4)

def has(p, flag):
    return (p & flag) != 0

print(has(perm, READ))       # True
print(has(perm, DELETE))     # False  （没开过删除）

perm = perm & ~WRITE         # 关掉写：7 & ~2 = 7 & 5 = 5 (只剩读+执行)
print(has(perm, WRITE))      # False
print(has(perm, READ))       # True

这就是权限系统、状态压缩（DP 里常见"用整数存访问过的状态"）的核心思想。一个整数，顶一堆布尔变量——既省空间，又让"组合判断"变得极快（一次 & 就查完）。

五、异或的魔力：找那个"只出现一次"的数

这大概是位运算里最经典、最让人拍大腿的一道题：

一个数组里，每个数都出现了两次，只有一个数出现了一次。找出它。要求 O(n) 时间、O(1) 空间。

普通思路得用哈希表计数（多花 O(n) 空间）。但用异或，三行搞定：

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

print(single_number([4, 1, 2, 1, 2]))   # 4

为什么？回想异或的三条性质：

1. x ^ x = 0 —— 成对出现的数，两两抵消为 0
2. x ^ 0 = x —— 0 不改变任何数
3. 交换律 —— 顺序无所谓

所以 4 ^ 1 ^ 2 ^ 1 ^ 2，把成对的 1、2 各自抵消成 0，最后剩下 4 ^ 0 ^ 0 = 4。出现两次的数全被"异或没了"，只剩那个孤独的数。

这一步，没有位运算，你很难写出更漂亮的答案。

六、复杂度分析：它到底快在哪

位运算的效率秘密就一句话：它是 CPU 的一条原生指令。

注意一个点：n & (n-1) 消最低位 1 的循环次数，等于"1 的个数"，而不是"总位数"。所以 count_ones 最坏 O(位数)，但平均比"逐位判断"快很多——尤其在数很"稀疏"（1 很少）的时候。

七、小结

1. 位运算就是"逐位对齐、独立计算"——& 要两个都 1，| 有一个 1 就行，^ 不同才是 1。
2. 左移乘 2、右移除 2；n & (n-1) 消掉最低位的 1——这是位运算的两个"肌肉记忆"。
3. 异或 x ^ x = 0 能抵消成对的东西——找唯一数、交换两数，全靠这一条。

八、动手实验：三件事都亲手敲一遍

实验 1：打印一个数的二进制

自己写一个函数，把任意正整数转成二进制字符串（不借助 bin）：

def to_binary(n):
    if n == 0:
        return "0"
    bits = []
    while n:
        bits.append(str(n & 1))   # 取末位
        n >>= 1                    # 右移一位
    return ''.join(reversed(bits))

print(to_binary(13))   # 1101
print(to_binary(100))  # 1100100

跑完你会发现，n & 1 取末位 + n >>= 1 右移，就是"逐位拆解"的标准套路。

实验 2：验证"左移乘 2、右移除 2"

for x in [1, 3, 7, 13, 100]:
    assert (x << 1) == x * 2
    assert (x >> 1) == x // 2
print("全部成立：左移=乘2，右移=整除2")

实验 3：挑战题——两个只出现一次的数

进阶一点：如果数组里有两个数只出现一次（其余都成对），怎么在 O(n) 时间 O(1) 空间内找出来？提示：先对所有数异或，得到 a ^ b；再用 a ^ b 里"某个为 1 的位"把数组分成两组，每组里就各只剩一个唯一数了。

def two_single_numbers(nums):
    xor_all = 0
    for x in nums:
        xor_all ^= x              # 得到 a ^ b
    # 找一个"区分位"：a 和 b 在这一位上不同
    diff = xor_all & (-xor_all)   # 取最低位的 1
    a = b = 0
    for x in nums:
        if x & diff:              # 按这一位是 0 还是 1 分组
            a ^= x
        else:
            b ^= x
    return [a, b]

print(two_single_numbers([1, 2, 1, 3, 2, 5]))   # [3, 5]（顺序可能相反）

diff = xor_all & (-xor_all) 是取"最低位 1"的经典写法（涉及补码，这里先背下来即可）。跑通它，你对异或的"分组抵消"就彻底吃透了。

先别急着往后翻。把实验 1 的 to_binary 亲手敲一遍，亲眼看到 13 变成 1101；再把实验 3 跑通，看到 [3, 5] 打印出来——位运算就不再是"头皮发麻的符号"，而是你手里最锋利的几把快刀之一。