位图算法通过手动管理整数数组和位运算，将布尔状态压缩至单比特，避免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 扫描快一个数量级
不复杂但容易忽略。
