位运算与位掩码（Bitmask）

位掩码把一个较小的非负整数集合编码到一个无符号整数中：第 i 位为 1 表示元素 i 在集合中。例如 0b1101 表示 {0, 2, 3}。这使集合运算变成 CPU 的按位运算，特别适合元素数量不大、需要高频状态转移或枚举子集的问题。

cpp

#include <bit>
#include <cassert>
#include <cstdint>
#include <limits>

using Mask = std::uint64_t;

uint64_t 最多直接表示 64 个元素。元素更多时，使用 std::bitset<N>（编译期固定大小）、动态位集或其他状态表示；不要把 1 << n 用在超出类型位宽的场景。

集合与位运算的对应

假设 a、b 都只使用全集 U 的有效位：

集合关系	位运算
交集 `A ∩ B`	`a & b`
并集 `A ∪ B`	`a
对称差 `A △ B`	`a ^ b`
差集 `A \ B`	`a & ~b`
补集 `U \ A`	`U ^ a`
`A` 是 `B` 的子集	`(a & b) == a`

补集必须相对于有限的全集计算，不能把 ~a 直接当成“数学上的补集”：~a 会把该整数类型的所有高位也置为 1。

C++ 中位运算符优先级容易误读，子集判断务必写括号：

cpp

if ((a & b) == a) { // A ⊆ B
    // ...
}

集合与单个元素

用 Mask{1} 构造位，避免 1 << i 先以有符号 int 运算：

cpp

constexpr unsigned width = std::numeric_limits<Mask>::digits;

Mask bit(unsigned i) {
    assert(i < width);
    return Mask{1} << i;
}

bool contains(Mask set, unsigned i) { return (set & bit(i)) != 0; }
Mask add(Mask set, unsigned i)        { return set | bit(i); }
Mask erase(Mask set, unsigned i)      { return set & ~bit(i); }
Mask toggle(Mask set, unsigned i)     { return set ^ bit(i); }

toggle 是翻转成员关系；只有已经确认 i 存在时，它才等价于删除。全集 {0, 1, ..., n-1} 的掩码可安全地构造为：

cpp

Mask lower_bits(unsigned n) {
    assert(n <= width);
    return n == width ? ~Mask{0} : (Mask{1} << n) - 1;
}

当 n == width 时必须特殊处理，左移恰好等于类型位宽是未定义行为。实际题目常限制 n <= 20 或 n <= 25，因为后续的 2^n 枚举才是主要瓶颈。

Lowbit 与 C++20 位操作 API

最低位的 1（lowbit）及其下标：

cpp

Mask lowbit(Mask s) { return s & (Mask{0} - s); } // s == 0 时结果也是 0

// 前提：s != 0
unsigned lowest_index(Mask s) {
    return std::countr_zero(s);
}

lowbit(s) 保留最低位的 1；s &= s - 1 删除最低位的 1。若 s 是 2 的幂，则 s & (s - 1) == 0。

C++20 <bit> 提供类型安全的标准接口（参数为无符号整数类型）：

cpp

int count = std::popcount(s);            // 1 的个数
bool one = std::has_single_bit(s);        // 是否恰好一个 1
unsigned tz = std::countr_zero(s);        // 末尾 0 的数量；s=0 时返回位宽
unsigned lz = std::countl_zero(s);        // 前导 0 的数量；s=0 时返回位宽
unsigned w  = std::bit_width(s);          // 二进制长度；s=0 时为 0

GCC/Clang 的 __builtin_popcountll、__builtin_ctzll 很常见，但后者传入 0 是未定义行为；__lg 也不是标准 C++ 接口。标准库函数更可移植。位操作通常会编译为少量机器指令，但具体性能仍取决于平台和编译器。

遍历集合中的元素

逐位扫描写法直观，时间 O(n)：

cpp

for (unsigned i = 0; i < n; ++i) {
    if (set & bit(i)) {
        // 处理元素 i
    }
}

如果集合很稀疏，直接删除最低位的 1，只迭代 popcount(set) 次：

cpp

for (Mask remaining = set; remaining != 0; remaining &= remaining - 1) {
    const unsigned i = std::countr_zero(remaining);
    // 处理集合中的元素 i
}

枚举状态、子集与超集

枚举全集所有子集

cpp

const Mask all = lower_bits(n);
for (Mask set = 0; set <= all; ++set) {
    // 处理 set
}

这会枚举 2^n 个状态，故只适合较小的 n。若 n == 64，不能用 set <= all 加一枚举，否则到最大值会溢出；实际状压题也远无法承受 2^64 个状态。

枚举某集合的所有子集

cpp

// 非空子集：从 set 到 1，按数值递减。
for (Mask sub = set; sub != 0; sub = (sub - 1) & set) {
    // sub 是 set 的一个非空子集
}

// 包含空集：显式在 sub == 0 时退出，防止回到 set。
for (Mask sub = set;; sub = (sub - 1) & set) {
    // sub 是 set 的一个子集
    if (sub == 0) break;
}

(sub - 1) & set 会删除 sub 的最低位 1，并只补回 set 中允许出现的低位，因此恰好跳转到下一个子集。若对每个集合再枚举其全部子集，总迭代次数为 3^n，不是 4^n，但依旧增长很快。

枚举某集合的所有超集

令 free = U \ base，每个超集都唯一写作 base | add，其中 add 是 free 的一个子集：

cpp

const Mask all = lower_bits(n);
const Mask free = all ^ base;
for (Mask add = free;; add = (add - 1) & free) {
    Mask superset = base | add;
    // 处理 superset
    if (add == 0) break;
}

异或的常用性质

异或满足交换律、结合律，并且 x ^ x == 0、x ^ 0 == x。因此成对出现的元素会抵消：

cpp

int unique_value = 0;
for (int x : nums) unique_value ^= x; // 其余元素均恰好出现两次时有效

它适合表达“奇偶性”或可逆的状态翻转；不要把异或误当作普通加法，x ^ y 没有进位。

位掩码 DP：状态压缩的桥梁

当问题状态由“哪些元素已选”决定时，可令 dp[mask] 表示集合 mask 的答案：

text

dp[mask] = 已选元素集合为 mask 时的最优值 / 可行性 / 方案数

典型转移是枚举一个未选元素 i，令 next = mask | (1ULL << i)；旅行商问题常见复杂度为 O(n²·2^n)，子集划分、选课依赖和小规模匹配也常用此表示。写转移前要先确定：掩码的每一位代表什么、初始状态是什么、答案在哪个掩码，以及 n 是否足以承受时间和内存。

安全清单

使用无符号类型做掩码；对负数或有符号左移不要假设位级行为；
移位前保证 0 <= shift < 类型位宽；
补集、差集和超集枚举必须限定全集 U；
countr_zero / lowbit 下标只在掩码非零时使用；
区分整数宽度：uint32_t、uint64_t 的 API 与字面量应匹配；
用位掩码前先估算 2^n、n·2^n、3^n，避免状态空间爆炸。

位运算与位掩码（Bitmask） ​

集合与位运算的对应 ​

集合与单个元素 ​

Lowbit 与 C++20 位操作 API ​

遍历集合中的元素 ​

枚举状态、子集与超集 ​

枚举全集所有子集 ​

枚举某集合的所有子集 ​

枚举某集合的所有超集 ​

异或的常用性质 ​

位掩码 DP：状态压缩的桥梁 ​

安全清单 ​

关联笔记 ​