7.4 位运算：整数的暗劲

7.4 位运算：整数的暗劲

本节摘要：位运算把整数看作一组开关：与、或、异或、取反、移位六个招式直接操作二进制位。心法只有三条——与用来"查位与清位"、异或满足自反（a 异或 b 再异或 b 还原回 a）、移位等效乘除二的幂。这门暗劲是并查集之外另一条极致路线：集合压进一个整数、子集枚举只要一条 (sub-1) & mask、找落单元素一遍异或。走火入魔高发于三处：运算优先级、负数右移、跨语言位宽。

把整数看成一组开关

前面六章的结构再精巧，落到机器里都是整数与地址。位运算就是直接拨弄这些整数的二进制位：二进制的每一位是一只开关，1 是亮、0 是灭。六个招式一张表就能列完，却撑起了权限系统、状态压缩、哈希扰动这些高频场景。

# 六个招式一次看完：a=13（1101）、b=6（0110）
a, b = 13, 6
print('a =', a, bin(a), '| b =', b, bin(b))
print('与 a&b =', a & b, bin(a & b), '：两位都是 1 才亮')
print('或 a|b =', a | b, bin(a | b), '：有一位是 1 就亮')
print('异或 a^b =', a ^ b, bin(a ^ b), '：两位不同才亮')
print('取反 ~a =', ~a, '：Python 无限位补码，等于 -a-1')
print('左移 a<<2 =', a << 2, '：二进制右补两个 0，等于乘 4')
print('右移 a>>2 =', a >> 2, '：砍掉低两位，等于整除 4')
# 输出：
# a = 13 0b1101 | b = 6 0b110
# 与 a&b = 4 0b100 ：两位都是 1 才亮
# 或 a|b = 15 0b1111 ：有一位是 1 就亮
# 异或 a^b = 11 0b1011 ：两位不同才亮
# 取反 ~a = -14 ：Python 无限位补码，等于 -a-1
# 左移 a<<2 = 52 ：二进制右补两个 0，等于乘 4
# 右移 a>>2 = 3 ：砍掉低两位，等于整除 4
​

招式虽六式，日常内力主要走两条：与（&）配掩码做"查位、清位、留位"，异或（^）做"抵消与还原"。其余招式多在造掩码时服役。

心法：三个不变式吃遍天

**不变式一：n 与 n-1 相与，恰好熄掉最低位的 1。**n-1 的本质是"把 n 的最低位 1 借走、其后所有 0 翻成 1"，两者相与，最低位 1 及其右侧全部归零、左侧原封不动。不变式二：n 与 -n 相与，恰好只剩最低位的 1（补码把取反加一变成了"从最低位 1 开始进位"）。不变式三：异或自反——同一把钥匙异或两次等于没动。

从 1100 里一次取出最低位的 1

三个不变式各配一个战场：

# 不变式实战：熄位链、lowbit、异或找落单者
n = 12                     # 1100
m, parts = n, []
while m:
    parts.append(str(m))
    m &= m - 1             # 不变式一：每按一次熄掉最低位的 1
print("熄位链：", " -> ".join(parts), "-> 0")   # 循环次数 = 1 的个数
print("lowbit =", n & (-n), "（不变式二：只剩最低位的 1）")

def count_bits(n):         # Brian Kernighan 位计数：只循环 1 的个数次
    c = 0
    while n:
        c += 1
        n &= n - 1
    return c
for x in (7, 12, 255):
    print(x, bin(x), "含 1 的个数：", count_bits(x))

nums = [4, 3, 3, 4, 9]     # 成对出现，只有一个落单
acc = 0
for x in nums:
    acc ^= x               # 不变式三：成对者互相抵消
print("落单元素 =", acc)
# 输出：
# 熄位链： 12 -> 8 -> 0
# lowbit = 4 （不变式二：只剩最低位的 1）
# 7 0b111 含 1 的个数： 3
# 12 0b1100 含 1 的个数： 2
# 255 0b11111111 含 1 的个数： 8
# 落单元素 = 9
# 位计数只需 1 的个数次循环，不是位数次——12 只转两圈
​

集合压进整数：状态压缩

一个 n 元素集合的全部子集共有 2 的 n 次方个，恰好对应 n 位二进制的全部取值——第 i 位是 1，就代表元素 i 在集合里。于是"选或不选"的每个组合成了一个整数，枚举子集退化成数数：

# 子集枚举：三个元素的集合，2 的 3 次方个子集
items = ['a', 'b', 'c']
n = len(items)
for mask in range(1 << n):              # 1<<n 即 2 的 n 次方
    chosen = [items[i] for i in range(n) if mask >> i & 1]   # 第 i 位为 1 就带上
    print("掩码", format(mask, '03b'), "（", mask, "）-> 子集 {", ", ".join(chosen), "}")
print("子集总数：", 1 << n)

# 枚举某个掩码的所有非空子集（含自身）：(sub-1)&mask 自动跳到下一个
mask = 0b101                             # 元素 0 与元素 2
sub, cnt = mask, 0
while sub:
    print("0b101 的子集：", bin(sub))
    sub = (sub - 1) & mask
    cnt += 1
print("非空子集共", cnt, "个（含自身）= 2 的 1 的个数次方减一")
# 输出：
# 掩码 000 （ 0 ）-> 子集 {  }
# 掩码 001 （ 1 ）-> 子集 { a }
# 掩码 010 （ 2 ）-> 子集 { b }
# 掩码 011 （ 3 ）-> 子集 { a, b }
# 掩码 100 （ 4 ）-> 子集 { c }
# 掩码 101 （ 5 ）-> 子集 { a, c }
# 掩码 110 （ 6 ）-> 子集 { b, c }
# 掩码 111 （ 7 ）-> 子集 { a, b, c }
# 子集总数： 8
# 0b101 的子集： 0b101
# 0b101 的子集： 0b100
# 0b101 的子集： 0b1
# 非空子集共 3 个（含自身）= 2 的 1 的个数次方减一
# `(sub-1)&mask` 三位以内绝不落空：减一翻位，与回 mask 收掉越界的 1
​

这套把戏叫状态压缩：第六章的背包若按"已选集合"定义状态（记录每件带没带，而非只记件数与重量），状态表就得用掩码当索引；旅行商问题的经典动态规划解法正是这么干的。集合运算全部换成位运算：并集用或、交集用与、差集借与非、判断属于看第 i 位。n 在二十出头以内时（掩码不超过百万量级），这条路又快又省。

⚠️ 常见坑：规模失控。状态压缩的表长随 n 指数膨胀，n 到三十上下时内存就会说话。先算 2 的 n 次方再决定动不动手。

💡 关键直觉：位运算是"把一层循环压进一次机器指令"。枚举子集从三层嵌套循环变成一趟数数、判断奇偶从取余变成看末位——复杂度没变，常数差出一个量级。工程上这叫常数优化，竞赛里这是过与不过的分界线。

走火入魔：三个高发事故现场

事故一：优先级想当然。1 << 2 + 3 不是"左移二再加三"：加法优先级更高，实际算的是 1 左移五。移位、位运算与加减混用时，括号不要省——这不是风格问题，是正确性问题。

**事故二：负数右移与位宽想当然。**Python 的右移向下取整，负数越移越向负无穷走；C 与 Java 的整数除法却向零截断，两套语义对不上。Python 整数还是无限精度，1 << 100 安然无恙；Java 的 int 移到第三十二位就溢出变号。跨语言搬代码时，位宽与符号行为先核对再跑。

**事故三：负移位数直接爆炸。**移位量小于零在任何主流语言里都是运行时错误，动态语言抛异常，静态语言多半是未定义行为——编译器不拦，上线才炸。

# 三个事故的现场复现
print(1 << 2 + 3)        # 加法先算：1 左移 5 = 32，不是 1 左移 2 加 3
print(-7 >> 1)           # Python 向下取整得 -4；C 与 Java 的 -7 除 2 截成 -3
try:
    print(1 << -1)       # 负移位数：当场报错
except ValueError as e:
    print("ValueError:", e)
print(len(str(1 << 100)), "位的数照算不误——Python 大整数，Java 的 int 早已溢出")
# 输出：
# 32
# -4
# ValueError: negative shift count
# 31 位的数照算不误——Python 大整数，Java 的 int 早已溢出
​

本节要点回顾

• 整数即开关：与配掩码查位清位、或并集、异或抵消还原、移位乘除二的幂，六招一张表；
• 三个不变式：n 与 n-1 熄最低位、n 与 -n 取最低位（7.2 节 lowbit 的身世）、异或自反找落单；
• 位计数只循环 1 的个数次（Brian Kernighan），12 转两圈、255 转八圈，输出可复算；
• 状态压缩把 n 元素集合压进掩码，枚举子集一趟数数、子集链一条 (sub-1) 与 mask；n 超过二十五就先算内存；
• 三大事故：优先级要括号、负数右移与位宽跨语言不同、负移位数当场爆炸。

暗劲到此修完，第七章收官，全册也到终点。七门内功——总纲的尺子、线性与树形的根基、图论的江湖、排序查找的兵器谱、五套范式拳法、四件高阶兵器——合在一起，才是"数据结构与算法"这四个字的分量。往后的路：把本册每节的实验亲手跑一遍，再挑一门开源实现读它的内部，内功才真正长在你身上。