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
第三步：set操作写入bit：data[index / 8] |= (1U 【index必须是非负整数且小于capacity，越界访问不检查】。
空间开销优化：动态分段+稀疏位图压缩
方法一：按数据分布切分成多个子Bitmap。例如将[0, 10⁹)划为1000段，每段10⁶范围，只对实际出现过数据的段分配内存；用unordered_map
方法二：对空段完全跳过，对稀疏段改用roaring bitmap逻辑——内部用container（16位整数数组）替代原始bit数组，当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)
③ 查找时用popcnt指令加速：if (__builtin_popcountll(word) == 0) continue; 跳过全零word，避免逐bit扫描；
④ 对高频查询场景，在Bitmap外层加一级L1缓存哈希表，缓存最近10000次get结果（key=index, value=bool），命中直接返回，避免访存——但【该缓存需配合LRU淘汰，否则内存泄漏】。
完整可运行源码（含main测试）
#include
#include
#include
#include
#include
using namespace std;
class Bitmap {
private:
vector
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 size_t word_idx = index / 64;
uint64_t bit_mask = UINT64_C(1) data[word_idx] |= bit_mask;
}
bool get(size_t index) const {
assert(index size_t word_idx = index / 64;
uint64_t bit_mask = UINT64_C(1) return (data[word_idx] & bit_mask) != 0;
}
};
int main() {
const size_t N = 100000000ULL;
Bitmap bm(N);
for (size_t i = 0; i auto start = chrono::steady_clock::now();
size_t count = 0;
for (size_t i = 0; i auto end = chrono::steady_clock::now();
cout (end - start).count() return 0;
}
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
