位运算与状态压缩

一句话定义

位运算（Bitwise Operations）把整数当作 32/64 位的布尔数组使用：一次 CPU 指令完成集合运算（与/或/异或/移位）；状态压缩（Bitmask）则用它表示「元素是否被选中」的集合状态，让含集合的 DP 与搜索获得 O(1) 的集合操作与几十倍的常数加速。

为什么重要

它是把「集合」这个抽象落到机器词上的最低成本方式：布隆过滤器（kp-010）、位图去重、状态压缩 DP（kp-028）、N 皇后位运算版都靠它；x & (x−1)、x & (−x) 这类惯用法也是面试常客。理解补码与移位语义，还能避免一类隐蔽的符号与溢出 bug。

前置知识

kp-002；二进制表示与补码常识；kp-028（状压 DP 的应用出口）。

核心概念

• 基本操作表：取第 i 位 x >> i & 1；置位 x | 1 << i；清位 x & ~(1 << i)；翻转 x ^ 1 << i；判空集 x == 0。
• 惯用法：x & (x−1) 消去最低位的 1（popcount 循环、判 2 的幂 x>0 && (x&(x−1))==0）；x & (−x) 取最低位的 1（lowbit，枚举子集/树状数组核心）；交换两数 a^=b; b^=a; a^=b（知道即可，工程别用）。
• 全集与枚举：全集 (1 << n) − 1；枚举全部子集 for (sub = S; sub; sub = (sub−1) & S)（含空集补一次）。
• 位图（Bitmap）：用 n 位表示 n 个布尔，空间 1/8 到 1/64；布隆过滤器、数据库 NULL 位图、位图索引同源。
• 语义陷阱：算术右移 vs 逻辑右移（Java >> 与 >>>；C/C++ 对负数右移是实现定义）；左移溢出；位运算优先级低于比较符，必须加括号。

原理与机制

位运算起作用的机制是「集合与二进制位的同构」：第 i 位为 1 ⇔ 元素 i 在集合中，于是交并补异或对应与或非异或，一次 CPU 指令并行处理 32/64 个元素。x & (−x) 恰好取出最低位的 1，源于补码表示：−x = 按位取反加一，取反使最低位的 1 之下的位错位互补，与运算后高位全部相消、只留那一位。枚举子集的 (sub−1)&S 则是「减一借位 + 与 S 掩码」的循环递减，保证不重不漏。

直观类比

一个 int 是一间有 32 个开关的配电房：与/或/异或就是「两排开关逐个按规则联动」，一次动作管 32 个开关——这就是并行的来源。状态压缩是「用一排灯表示去过哪些城市」：灯的编号组合即状态，集合运算变成一盏灯的开关。

公式或模型

• popcount 两种实现：

// 朴素: 逐位消 1，循环次数 = 1 的个数
c ← 0 ; 当 x ≠ 0: x ← x & (x−1) ; c++
// 内建: 编译器单指令（CPU popcnt），工程首选
__builtin_popcount(x) / Integer.bitCount(x)

• 复杂度视角：n 元集合的枚举从回溯的「分支树」变成 mask 的 2ⁿ 次循环，内层集合运算 O(1)；「枚举 S 的所有子集」总量 Σ_C(n,k)·2^k = 3ⁿ（用 (sub−1)&S 技巧），这是状压 DP 复杂度的常见底数。

图示

x = 0b101100 (=44)
x−1       = 0b101011
x&(x−1)   = 0b101000    ← 消去最低位的 1（第 2 位）
x&(−x)    = 0b000100    ← 只剩最低位的 1（lowbit）

子集枚举 S = 0b1101:
1101 → 1100 → 1001 → 1000 → 0101 → 0100 → 0001 → 0000  （倒序穷尽）

实例或案例

• 布隆过滤器与位图：10⁷ 个 32 位整数去重只需 10⁷/8 ≈ 1.2MB（另见 kp-010）。
• N 皇后位运算：用三个整数表示列/两条对角线的占用，avail = 全集 & ~(col|ld|rd)，p = avail & −avail 枚举放置，常数缩小一个量级。
• 状压 DP（kp-028）：TSP、覆盖问题、棋盘轮廓线 DP。
• 权限系统：一个 int 的 32 位各表一项权限，鉴权即 (mask >> bit) & 1；TCP flags、数据库行头同样按位打包。

常见误区

• 位运算不加括号：x & 3 == 2 实为 x & (3==2)（C/Java 中 == 优先级更高），经典静默错误。
• 负数右移想当然：有符号数算术右移补符号位，-1 >> k 恒为 −1；需要逻辑移位用 >>>（Java）或先转无符号。
• 1 << 40 在 32 位整型下溢出：位宽必须与数据类型匹配（64 位用 1L << 40）。
• 异或交换两个同一变量（a^=a 自清零）或以为它更快：现代 CPU 上反而更慢且易错，用临时变量。
• 用位运算优化本身是 O(n²) 的算法：位运算只压常数，不降复杂度。

自测题

1. 写出「判断 x 是否为 2 的幂」的一条表达式并解释。

答案要点：x > 0 && (x & (x−1)) == 0——2 的幂二进制只有一位 1，减一后与其与运算为 0。

1. 手推 S=0b1011 的子集枚举序列（用 (sub−1)&S）。

答案要点：1011 → 1010 → 1001 → 1000 → 0011 → 0010 → 0001 → 0000。

1. popcount(0b11101100) 是多少？给出两种求法。

答案要点：5；消最低位循环 5 次，或内建 popcount 指令。

与其他知识点的关系

kp-010 布隆过滤器与位图同构；kp-028 状压 DP 是最大应用面；kp-027 回溯的位运算版（N 皇后）是剪枝加速器；kp-009 的「桶」与「位段」是同一思想的两种粒度。

延伸阅读

《Hacker's Delight》（Warren）——位运算技巧的百科；CLRS 关于位向量与 van Emde Boas 的对比可作进阶。