Bitmap算法适用于已知范围的非负整数去重与存在性查找，以O(N/8)空间实现高效位操作；其核心是通过字节索引与位偏移映射整数，并用位运算完成设置与查询。
当需要对海量整数数据进行去重与存在性查找时，若数据范围已知且集中于非负整数区间，Bitmap（位图）算法可显著降低空间开销并提升查询效率。以下是基于 C++ 实现的 Bitmap 算法设计与优化方案：
一、基础 Bitmap 实现
该方法使用 std::vector
1、定义 Bitmap 类，内部使用 std::vector
2、实现 set(int x) 方法：计算字节索引 byte_idx = x / 8，位偏移 bit_idx = x % 8，执行 data[byte_idx] |= (1
立即学习“C++免费学习笔记（深入）”；
3、实现 test(int x) 方法：同样计算 byte_idx 和 bit_idx，返回 (data[byte_idx] & (1
4、实现 count() 方法：遍历所有字节，对每个字节调用内置 __builtin_popcount 或查表法统计置位数。
二、内存对齐与缓存友好优化
原始逐字节访问易引发缓存行未命中，尤其在高密度写入时。通过按 64 位或 128 位对齐分配内存，并批量处理连续整数，可提升 CPU 缓存命中率与指令吞吐量。
1、将底层存储改为 std::vector
2、set_range(int start, int end) 方法中，对首尾非对齐部分单点操作，中间对齐段使用 uint64_t 原子赋值或 _mm256_store_si256（需启用 AVX）。
3、在构造函数中使用 aligned_alloc(64, size) 分配内存，确保起始地址 64 字节对齐。
4、禁用 vector
三、分段 Bitmap（Segmented Bitmap）
当数据范围极大（如 0–10⁹）但实际分布稀疏时，全量分配位图将浪费大量内存。分段策略将大范围划分为固定大小的桶（如每桶覆盖 65536 个整数），仅对有数据的桶分配内存。
1、定义桶大小 BUCKET_SIZE = 1 > 16，桶内偏移 local_idx = x & 0xFFFF。
2、使用 std::unordered_map
3、set(int x) 中先检查 bucket_id 是否存在，不存在则 new uint8_t[BUCKET_SIZE / 8] 并初始化为零。
4、test(int x) 时若 bucket_id 不在 map 中，直接返回 false；否则查对应桶内 local_idx 对应位。
四、并发安全增强版本
在多线程插入场景下，多个线程可能同时修改同一字节的不同位，需保证位操作原子性。直接使用锁粒度过大会降低吞吐，应采用细粒度原子位操作。
1、底层存储改用 std::vector<:atomic>>，每项管理 64 个连续整数。
2、set(int x) 中定位 atomic_uint64_t& atom = data[x / 64]，再用 fetch_or(1ULL
3、test(int x) 使用 load(std::memory_order_acquire) 获取当前值后测试对应位，禁止使用非原子读取配合原子写入的混合模式。
4、若编译环境不支持 64 位原子类型，则降级为 std::vector<:atomic>>，每字节管理 8 位，以牺牲空间换取兼容性。
五、Roaring Bitmap 替代方案集成
当数据呈现块状聚集（如 [1000–1999], [5000–5999]）时，传统 Bitmap 空间利用率骤降。Roaring Bitmap 将区间按 16 位分片（container），对稀疏片用 bitmap，密集片用 array 或 run，兼顾压缩比与速度。
1、引入 roaring.h 头文件（C 接口）或 CRoaring C++ 封装库。
2、构造 roaring_bitmap_t* rb = roaring_bitmap_create();，插入使用 roaring_bitmap_add(rb, x)。
3、去重合并多个 Bitmap 时调用 roaring_bitmap_or_inplace(dst, src)，比逐个插入快一个数量级。
4、序列化导出使用 roaring_bitmap_serialize(rb, buf) 避免运行时重建开销，roaring_bitmap_t 内部自动选择 container 类型，无需人工干预分段逻辑。
