位图算法通过手动管理整数数组和位运算，将布尔状态压缩至单比特，避免bool类型默认占1字节的浪费，使空间利用率提升8倍；其核心是用uint64_t等整数数组承载比特流，通过字索引（i>>6）和位偏移（i&63）定位目标位，再以原子位运算实现置位、清位与测试。

位图算法把 boolean 的“真/假”压缩到单个比特位，不是靠语言语法糖，而是靠手动管理内存单元 + 位运算。它绕开了 bool 类型默认占 1 字节的底层限制，让每个状态只吃 1 bit —— 空间利用率直接提升 8 倍。

为什么必须跳过标准 bool 数组

多数语言中，bool 是最小可寻址单位，但不是最小存储单位。系统分配内存时，哪怕只存一个 true，也会划出至少 1 字节（8 bit）。存 100 万个 bool，实际占用约 1MB；而位图只需约 125KB。更关键的是，高频访问下，[]bool 会引发更多缓存未命中和 GC 压力，尤其在 Go、Java 或 C++ 中表现明显。

核心实现：用整数数组承载比特流

位图不直接操作 bit，而是用 uint64_t、uint32_t 或 byte[] 这类固定宽度整数数组作为底层载体。每个整数负责管理一批 bit（如 uint64 管 64 个状态），通过两个计算定位目标 bit：

• 字索引：i / 64 或 i >> 6 → 找到第几个 uint64 元素
• 位偏移：i % 64 或 i & 63 → 找到该元素内第几个 bit（从最低位 bit 0 开始）

例如数字 137：137 >> 6 = 2，137 & 63 = 9，表示它落在第 2 个 uint64 的第 9 位（即 2⁹ 位置）。

三个原子操作的位运算写法

所有功能都基于这三个基础操作，且必须用无符号整数类型避免符号扩展或移位未定义行为：

• 置位（Set）：bits[wordIdx] |= (1ULL
• 清位（Clear）：bits[wordIdx] &= ~(1ULL
• 查位（Test）：(bits[wordIdx] & (1ULL

注意：1ULL 是关键 —— 使用 64 位无符号字面量，防止左移溢出；bitIdx 必须已对 64 取模，否则 1 在 Go/C 中可能为 0 或 UB。

边界与工程细节不能忽略

手写位图不是“写完 set/get 就完事”，真实场景需处理：

• 动态扩容：插入超出当前容量的索引时，需按 word 单位追加 uint64 元素，而非逐 byte 分配
• 越界语义：对未分配的 word 索引，Get 应返回 false（逻辑上默认未设置），Set 则触发 grow
• 批量操作优化：清空连续区间时，不要循环调用 Clear；应计算起止 word，整块赋 0，首尾用掩码处理残余 bit
• 遍历效率：用 ctz（count trailing zeros）指令跳过前导 0，配合 x & (x-1) 清除最低位 1，比逐 bit 扫描快一个数量级

不复杂但容易忽略。