适用读者：觉得位运算是"炫技"，不确定什么时候该用的人。
前置：S03-B01。
实测环境：Python 3.12.3（sys.getsizeof与位运算验证）；实测日期 2026-11-05。
覆盖旧文：A-1513（位运算，246 点）。
覆盖扩展：E-S03-011（位图与 Succinct 结构）。
上一篇：S03-B07 · 图与并查集：连通性怎么维护
下一篇：S03-B09 · 数学算法集。
1. 一句话结论
位运算不是炫技，它解决两个具体问题：① 用 1 个 bit 表示"是/否"以省内存；② 把"集合运算"压缩成一条 CPU 指令。
| 用途 | 收益 | 例子 |
|---|---|---|
| 状态压缩 | 内存降一个数量级 | 权限位、开关集合、去重标记 |
| 集合运算 | O(1) 完成交/并/差 | 权限判断、布隆过滤器 |
| 位级技巧 | 常数级优化 | n & (n-1) 清最低位 |
| DP 状态压缩 | 把 2ⁿ 状态塞进整数 | 旅行商、棋盘覆盖 |
2. 实测：位掩码到底省多少
10 万个"开关"：
| 表示 | 内存 |
|---|---|
[False] * 100000（Python 布尔列表） |
781 KB |
位掩码（bytearray / 整数位） |
12.2 KB |
| 比值 | 64× |
这就是位图的本质：一个字节存 8 个状态。数据库的位图索引、Linux 的 CPU 亲和性掩码（cpu_set_t）、文件权限（rwx）都是这个思路。
注意：Python 的
int是任意精度，1 << 100000会分配 12.5 KB 的大整数；Java/C 里用long[]手写位图更常见。
3. 六个必会技巧（均已验证）
| 技巧 | 表达式 | 作用 |
|---|---|---|
| 清最低位的 1 | n & (n - 1) |
循环用它可统计 1 的个数 |
| 取最低位的 1 | n & -n |
树状数组（Fenwick）的基础 |
| 判断是否 2 的幂 | n > 0 && (n & (n-1)) == 0 |
一条指令 |
| 第 k 位置 1 | n | (1 << k) |
集合添加元素 |
| 第 k 位清 0 | n & ~(1 << k) |
集合删除元素 |
| 第 k 位查询 | (n >> k) & 1 |
集合包含判断 |
实测验证：
n&(n-1) 清最低位: 0b101100 → 0b101000
x&-x 取最低位1: 0b101100 → 0b100
popcount(0b101101) = 4
3.1 popcount 的循环写法
int count = 0;
while (n != 0) { n &= (n - 1); count++; } // 循环次数 = 1 的个数
对比"逐位检查"的 32 次循环，只循环 popcount 次。
4. 集合运算：位运算是天然的集合代数
| 集合操作 | 位运算 |
|---|---|
| 交集 | A & B |
| 并集 | A | B |
| 差集（A 减 B） | A & ~B |
| 对称差 | A ^ B |
| 判断 B ⊆ A | (A & B) == B |
权限系统的最小实现（Java）：
static final int READ = 1 << 0, WRITE = 1 << 1, EXEC = 1 << 2;
int perm = READ | WRITE; // 授权
boolean canRead = (perm & READ) != 0; // 判断
perm &= ~WRITE; // 撤权
为什么比 Set<Enum> 好：内存 4 字节 vs 对象开销；判断是一条指令；可序列化成整数存库。
5. 状态压缩 DP（什么时候必须用）
当"状态"是"哪些元素被选过"时，用整数表示集合：
状态 = 一个 bitmask，第 i 位 = 是否已访问 i
dp[mask][last] = 最短路径长度
规模上限：n ≤ 20 左右（2²⁰ = 100 万状态）。超过就别用状态压缩（复杂度指数级）。
判据：题目里出现"n ≤ 20"或"每个元素只能选一次" → 想状态压缩。
6. 有符号数的坑（Java/C 必读）
| 现象 | 原因 |
|---|---|
-1 >> 1 结果还是 -1 |
算术右移（符号位扩展） |
-1 >>> 1 = 2147483647 |
逻辑右移（补 0） |
1 << 31 是负数 |
溢出到符号位 |
Math.abs(Integer.MIN_VALUE) 返回负数 |
绝对值溢出 |
规矩：位运算只用 >>>（逻辑右移）做无符号场景；涉及负数时先转 long。
7. 五个误区
| 误区 | 真相 |
|---|---|
| "位运算一定更快" | 现代编译器优化后，可读性更重要；只在"集合/状态"场景有实质收益 |
| "位掩码可以无限扩展" | 受整数位宽限制（32/64），超了要数组 |
">> 和 >>> 一样" |
负数时不同（算术 vs 逻辑） |
| "位运算只能用于整数" | 浮点不能用位运算（除 Double.doubleToLongBits 这类转换） |
| "位图适合稀疏数据" | 稀疏数据用位图会浪费（考虑 Roaring Bitmap 等压缩位图） |
8. 自检
- 10 万开关用布尔列表与位掩码，内存差多少倍（实测值）？
- 用
n & (n-1)怎么统计 1 的个数？循环几次？ - 用位运算实现"判断 B 是 A 的子集"。
-1 >> 1与-1 >>> 1分别是什么？- 什么规模的 n 才适合状态压缩 DP？
9. 下一篇
S03-B09 · 数学算法集：从阶乘到 FFT
位运算处理离散状态，下一篇处理数值：阶乘溢出边界、素数筛为什么比试除快 300 倍（实测 3.7 ms vs 1,167 ms）、快速幂为什么快一万倍，以及 FFT 在工程里的真实用途。
本篇属于系列《S03 · 数据结构与算法》。旧文来源：A-1513；扩展点 E-S03-011。内存对照（781 KB vs 12.2 KB）与位技巧验证为 2026-11-05 实测。