状态压缩DP必须用&、|、^和(1<<i)等位运算，因为其核心是用二进制整数紧凑表示集合状态（如第i位为1表示元素i已选），而这些运算能高效实现状态判断（x&(1<<i)）、添加（x|(1<<i)）、删除（x&~(1<<i)）和翻转（x^(1<<i)）等操作。
状态压缩 DP 为什么必须用 &、|、^ 和 (1
因为状态压缩的本质是把一个布尔数组（比如哪些物品已选、哪些点已访问）压成一个整数，而位运算是唯一能高效读写单个“开关位”的手段。用 vector<bool></bool> 或 int[] 模拟，常数直接翻几倍，DP 状态数一多就超时。
常见错误现象：dp[mask] = min(dp[mask], dp[mask - 1] + cost) —— 这里 mask - 1 不是“去掉第 0 位”，而是减法运算，可能清掉多个位甚至借位，逻辑全错。
- 判断第
i位是否为 1：用mask & (1 ，不是 <code>mask & i（i不是掩码） - 把第
i位设为 1：用mask | (1 ，不是 <code>mask + (1 （虽然结果有时一样，但语义不清，且不适用于重复设置） - 把第
i位设为 0：用mask & ~(1 ，不是 <code>mask ^ (1 （异或会翻转，不是强制置 0）
初始化和转移时怎么避免越界和重复计算
状态压缩 DP 的 mask 范围固定是 [0, 1 ，但并非所有 <code>mask 都合法。比如旅行商问题中，起点必须在 mask 中；集合覆盖中，某些元素不能单独出现。
典型错误：for (int mask = 0; mask 之后直接枚举子集用 <code>for (int sub = mask; sub; sub = (sub - 1) & mask)，但没检查 sub 是否满足前置约束（如必须包含起点），导致无效转移污染答案。
立即学习“C++免费学习笔记（深入）”；
- 初始化只设合法初态：例如 TSP 从节点 0 出发，只设
dp[1 ，其余为 <code>INF - 枚举子集前加守卫：比如要求子集必须含节点 0，则写
if (!(sub & 1)) continue; - 转移时用
if (dp[sub][j] != INF)判有效，而不是靠初始化值“侥幸”跳过
__builtin_popcount 在循环里调用会不会变慢
不会。GCC/Clang 下 __builtin_popcount 编译后就是一条 popcnt 指令（x86-64），延迟约 1–3 周期，比手写循环数位快一个数量级。但要注意：它的输入是 unsigned int，传入 long long 可能截断——该用 __builtin_popcountll。
常见错误现象：本地测得快，交题 WA 或 TLE —— 很可能是用了 __builtin_popcount(mask) 处理 n > 31 的情况，高位被丢弃，状态误判。
- n ≤ 31：用
__builtin_popcount(mask) - n ≤ 63：必须用
__builtin_popcountll(mask) - 跨平台或怕编译器不支持？手写查表：静态数组
char popcount[65536]，按 16 位分段查
二维状态 dp[mask][i] 的内存和访问局部性怎么优化
直接开 dp[1 是 20 × 2²⁰ ≈ 20MB，看似可接受，但 CPU cache 行（64 字节）只能装 8 个 <code>int，而 mask 维度跨度大，dp[mask][i] 和 dp[mask][i+1] 地址差 4 × (1
实际跑起来比理论慢 3–5 倍很常见，尤其在 n=20 以上时。
- 把维度换序：
dp[i][mask]让i在外层，内层mask连续访问，cache 友好 - 滚动数组：如果转移只依赖上一层
i-1，就只存两行，省空间也提升预取效率 - 用
vector<vector>></vector>而非int dp[N][M]静态数组？别——前者指针跳转更差；优先用一维vector<int> dp(1 + 手动偏移计算</int>
状态压缩 DP 的边界特别硬：1 << n 一旦超 int 范围（n ≥ 31），mask 就溢出；位运算优先级又低，mask & 1 << i 实际是 mask & (1 << i)，但漏括号会变成 (mask & 1) << i，这种 bug 很难靠输出调试发现。
