位图是针对特定整数范围的高效存在性标记工具，用1个bit表示一个整数是否出现，空间压缩至理论极限；其核心是手动管理字节数组与位偏移，需用uint8_t等原生类型而非std::vector，并支持分桶、映射等策略应对超大值域。
位图（bitmap）不是万能容器，而是针对特定整数范围的高效存在性标记工具。它用1个bit表示一个整数是否出现过，把空间压缩到理论极限——比如10亿个整数去重，仅需约125mb内存，比用std::unordered_set省32倍以上。
为什么不能直接用 std::vector
它不是真正意义上的位数组。C++标准规定std::vector是特化类型：底层按位存储，但接口伪装成普通容器。这导致几个硬伤：
- 迭代器解引用返回代理对象，不能取地址（
&v[i]非法） - 没有
data()接口，无法获取原始字节数组指针 - 不支持位运算原语（如
|=、&=），无法精准控制单个bit - 映射逻辑必须自己写，而它连基础支撑都不提供
正确实现位图的三要素
核心是手动管理字节+位偏移，推荐用std::vector或std::unique_ptr：
-
内存分配：大小为
(max_val + 7) / 8字节（向上取整到字节） -
设值：
bits[n >> 3] |= (1 （右移3位等价于除8，&7等价于模8） -
查值：
(bits[n >> 3] & (1
注意：若原始数据含负数或值域极大（如全量int32），必须先做映射（如加偏移转非负）或分桶（如按高8位分256桶），否则内存爆炸。
如何应对超大值域（比如40亿无符号整数）
全量uint32需512MB位图，看似可行，但实际数据往往稀疏。更稳健的做法是分治：
- 按高位哈希分桶：例如
n >> 24作为桶号，共256桶 - 每桶独立申请内存，大小由该桶内实际数据范围决定（非全局最大值）
- 插入时：先算桶号，再用
n & 0xFFFFFF取低24位作桶内索引 - 查询时需遍历相关桶（通常只需查1个），不牺牲精确性
去重后怎么拿到所有“出现过的数”
位图只存状态，不存值。遍历本质是扫描+解码：
- 不要写
for (int i = 0; i 逐个判断——这是O(N)，但N是值域上限，可能远大于实际数据量 - 推荐按字节/字扫描：对每个
uint8_t查__builtin_popcount，再用__builtin_ctz定位每个置位bit - 若用
uint64_t数组，可批量处理64位，效率更高；注意用aligned_alloc保证64字节对齐
不复杂但容易忽略。
