位向量本质是用单个比特表示元素存在性，将集合压缩为二进制位序列，仅存“有/无”信息，故空间极省、操作极速；其构造需通过整数数组模拟，利用位运算实现字定位（i >> 5）和位偏移（i & 0x1F）寻址。

位向量本质是用单个比特表示一个元素的存在性，把集合压缩成二进制位序列。它不存数据本身，只存“有没有”，因此空间极省、操作极快——所有核心操作（查、增、删、集合运算）都是常数时间的位指令。

位向量怎么构造：从整数数组到单比特寻址

编程语言没有原生 bit 数组，所以要用 int 或 uint64_t 数组模拟。关键在两个映射：

• 定位字（word）下标：元素 i 属于第 i / bits_per_word 个整数，例如 32 位系统中用 i >> 5（因 2⁵ = 32）
• 定位位偏移：元素 i 在该整数内的第 i % bits_per_word 位，即 i & 0x1F

比如要标记数字 37：37 ÷ 32 = 1 → 查第 1 个 int；37 % 32 = 5 → 置该 int 的第 5 位（从 0 开始）为 1，即执行 data[1] |= (1U 。

核心操作全靠三行位指令

所有动作都围绕“掩码 + 位运算”展开，无循环、无分支：

• 设存在：data[i >> 5] |= (1U
• 清不存在：data[i >> 5] &= ~(1U
• 查是否存在：(data[i >> 5] & (1U

注意使用无符号类型（如 uint32_t）避免右移时符号扩展；左移前确保位索引不越界（）。

集合运算直接对应位运算符

两个位向量 a 和 b（同长度），集合关系天然映射为位逻辑：

• 并集 A ∪ B → a | b（某位只要一个为 1，结果就为 1）
• 交集 A ∩ B → a & b（仅当两位都为 1，结果才为 1）
• 差集 A − B → a & ~b（保留 a 中 b 没有的位）
• 补集 ¬A（全集内） → ~a（需限定有效位宽，避免高位干扰）

若用 std::bitset，这些就是一行调用：bitset_a |= bitset_b、auto inter = bitset_a & bitset_b。

实战统计：快速枚举与计数

不遍历所有位，只处理已置位：

• 统计元素个数：用内置函数，如 C++ __builtin_popcount(a)（32 位）、__builtin_popcountll(b)（64 位），或 bitset::count()
• 遍历所有元素：用 lowbit 技巧逐个提取： while (mask) {
    int x = __builtin_ctz(mask); // 最低位 1 的位置
    // 处理 x
    mask &= mask - 1; // 清掉最低位 1
  }
• 判断空集：mask == 0；判断全集（假设 w 位）：mask == (1ULL

这种统计方式时间复杂度正比于集合大小，而非定义域大小，对稀疏集合尤其高效。