Bitmap位图算法可将10亿非负整数去重压缩至125MB内存，单次查询O(1)；需先确认值域范围，负数或超大值须映射或换Roaring Bitmap；手写Bitmap类用位运算加速，读取时校验越界，遍历输出为O(N)值域复杂度。

用C++处理十亿级整数去重时，内存爆满、哈希冲突频繁、STL set插入慢到卡死——此时Bitmap位图算法能将10亿个int压缩进125MB内存，单次查询稳定在O(1)。它不存原始值，只标记存在性，专为非负整数密集区间设计。

确定数据范围与位图大小

先确认待处理整数的取值范围：若全为[0, 999999999]内的非负整数，则最大值N = 999999999；位图需至少N+1个比特位，即需 ⌈(N+1)/8⌉ 字节内存。计算得：⌈1000000000/8⌉ = 125000000 字节 ≈ 125MB。

若数据含负数或超大值（如大于2^31-1），【Bitmap方案不可直接使用，必须先做偏移映射或改用Roaring Bitmap等扩展结构】。

这一步不能跳过——位图大小错一位，后续所有位操作都会整体偏移，结果完全错误。

立即学习“C++免费学习笔记（深入）”；

手写高效Bitmap类核心接口

方法一：基于vector封装（简洁但可能被优化成代理对象）

声明 class Bitmap { private: std::vector bits; public: explicit Bitmap(size_t max_val) : bits(max_val + 1, false) {} void set(size_t x) { if (x

方法二：手动管理uint64_t数组（性能更高，推荐）

用 uint64_t* data 指针 + size_t size_in_bits 构造；set(x) 时计算 data[x >> 6] |= (1ULL > 6] & (1ULL

注意：x >> 6 等价于 x / 64，x & 63 等价于 x % 64，位运算比除法快一个数量级。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

加载海量数据并完成去重

第一步：打开输入文件流，逐行读取整数字符串。

第二步：对每个字符串调用 std::stoul 转为 unsigned long；若原始数据为有符号int且确认无负值，可用 static_cast(x) 避免异常开销。

第三步：检查数值是否越界——若 x > max_val，【直接丢弃或记录为异常，绝不可传入set()，否则触发越界写入导致段错误】。

第四步：调用 bitmap.set(x) 标记该数存在。此操作是原子的、无锁的、纯CPU指令，每秒可执行千万次以上。

第五步：全部读完后，遍历 bitmap.test(i) 为 true 的所有 i，输出或存入结果容器。遍历本身是O(N)，但N是值域上限而非数据量，即使原始数据只有1万个，也要扫完10亿位——这是Bitmap的时间代价。

源码整合与编译运行

将上述Bitmap类、main函数中文件读取逻辑、命令行参数解析（如./a.out input.txt 1000000000）合并为 single-file.cpp。

用 g++ -std=c++17 -O2 -march=native single-file.cpp -o bitmap；确保开启-O2，否则vector的代理访问会拖慢3倍以上。

运行前检查可用内存：free -h 中的available值必须大于130MB，否则malloc失败时程序会abort。