Bitmap算法可将十亿级整数去重压缩至125MB以内并支持O(1)查重：1. 按范围计算字节数（如[0,10⁹)需125MB）；2. 封装Bitmap类，用uint64_t数组+位运算实现set/get；3. 通过分段、Roaring Bitmap、热区优化节省空间；4. 利用cache对齐、popcnt指令和L1缓存提升性能。
用C++处理十亿级整数去重时，内存爆满、哈希表太慢、排序+双指针无法流式处理——此时必须用Bitmap算法把10⁹个int压缩进125MB以内，并支持O(1)查重。
Bitmap基础实现：用bit位代替bool数组
第一步：计算所需字节数。32位有符号整数范围是[-2147483648, 2147483647]，共2³²个值，但实际常用非负整数场景只需覆盖[0, N)，N取最大可能值；若已知数据全在[0, 1000000000)，则申请ceil(1000000000/8) = 125000000字节（约119.2MB）。
第二步：封装Bitmap类，用vector<uint8_t>存储，下标i对应第i个bit；设bit位置为index，则byte索引为index / 8，位偏移为index % 8。
第三步：set操作写入bit：data[index / 8] |= (1U << (index % 8))；get操作读取bit：(data[index / 8] & (1U << (index % 8))) != 0。注意【index必须是非负整数且小于capacity，越界访问不检查】。
立即学习“C++免费学习笔记（深入）”；
空间开销优化：动态分段+稀疏位图压缩
方法一：按数据分布切分成多个子Bitmap。例如将[0, 10⁹)划为1000段，每段10⁶范围，只对实际出现过数据的段分配内存；用unordered_map<int, unique_ptr<Bitmap>>管理，key为段起始编号（如段i覆盖[i×10⁶, (i+1)×10⁶)）。
方法二：对空段完全跳过，对稀疏段改用roaring bitmap逻辑——内部用container（16位整数数组）替代原始bit数组，当container内数值个数<4096时用有序数组，否则升级为bitmap container。这需要引入roaringbitmap库或手写container切换逻辑。
方法三：若数据集中在某几个区间（如日志时间戳集中在最近7天），可先做预扫描统计热区，仅对热区启用高精度Bitmap，冷区用布隆过滤器粗筛+外部磁盘归并去重。这一步节省空间最显著，但需额外I/O调度逻辑。
查找性能提升：并行位操作+缓存友好布局
① 将Bitmap内存按64字节对齐（_aligned_malloc或posix_memalign），确保每次cache line加载能覆盖8个连续uint64_t；
② 把uint8_t数组改为uint64_t数组，一次处理64个bit：set操作用mask = UINT64_C(1) << (index % 64)，target_word |= mask；
③ 查找时用popcnt指令加速：if (__builtin_popcountll(word) == 0) continue; 跳过全零word，避免逐bit扫描；
④ 对高频查询场景，在Bitmap外层加一级L1缓存哈希表，缓存最近10000次get结果（key=index, value=bool），命中直接返回，避免访存——但【该缓存需配合LRU淘汰，否则内存泄漏】。
完整可运行源码（含main测试）
#include <iostream>
#include <vector>
#include <cstdint>
#include <cassert>
#include <chrono>
using namespace std;
class Bitmap {
private:
vector<uint64_t> data;
size_t capacity_bits;
public:
explicit Bitmap(size_t n) : capacity_bits(n), data((n + 63) / 64, 0) {}
void set(size_t index) {
assert(index < capacity_bits);
size_t word_idx = index / 64;
uint64_t bit_mask = UINT64_C(1) << (index % 64);
data[word_idx] |= bit_mask;
}
bool get(size_t index) const {
assert(index < capacity_bits);
size_t word_idx = index / 64;
uint64_t bit_mask = UINT64_C(1) << (index % 64);
return (data[word_idx] & bit_mask) != 0;
}
};
int main() {
const size_t N = 100000000ULL;
Bitmap bm(N);
for (size_t i = 0; i < N; i += 17) bm.set(i);
auto start = chrono::steady_clock::now();
size_t count = 0;
for (size_t i = 0; i < N; ++i) if (bm.get(i)) ++count;
auto end = chrono::steady_clock::now();
cout << "Count: " << count << ", time: " << chrono::duration_cast<chrono::milliseconds>(end - start).count() << "ms\n";
return 0;
}
