c++oding="utf-8" ?>

bitmap位图算法用vector实现，每个元素管32位；桶数=(max_value+31)/32，位偏移x&0x1f，桶索引x>>5；提供set、test、clear原子操作，全程位运算无除法。

用C++处理上亿整数去重时，内存爆满、哈希表太慢、排序+双指针又耗时——Bitmap位图算法能将10亿个int的去重压缩到125MB内存内，且单次查询仅需一次位运算。

设计Bitmap核心数据结构

定义一个支持32位无符号整数范围（0～4294967295）的位图类，底层用vector存储，每个uint32_t管理32个bit。

计算所需桶数量：(max_value + 31) / 32 → 向上取整，例如处理[0, 100]需4个uint32_t（128位）。

位偏移用 value & 0x1F 快速等价于 value % 32；桶索引用 value >> 5 等价于 value / 32；这两个位运算避免除法开销，【必须用无符号右移>>>，否则负数会出错】。

构造函数初始化vector大小为bucket_count，全部置0。

实现set、test、clear三个原子操作

方法一：set(int x) —— 将第x位设为1。先检查x是否在有效范围内（0 ≤ x ≤ UINT32_MAX），再计算bucket_idx = x >> 5，bit_offset = x & 0x1F，执行bits[bucket_idx] |= (1U

方法二：test(int x) —— 返回第x位是否为1。同样校验x范围后，返回 (bits[x >> 5] >> (x & 0x1F)) & 1U。

方法三：clear(int x) —— 将第x位清零。使用 bits[x >> 5] &= ~(1U

这三个操作全部是O(1)，无分支、无循环、无函数调用，CPU缓存友好。

批量加载并去重海量整数

第一步：读取输入源（如文件或stdin），逐行解析整数。遇到非数字行直接跳过，不抛异常——防止脏数据中断流程。

C++ Code Review Master

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

下载

第二步：对每个合法整数x，调用bitmap.set(x)。注意：若x超出预设范围（如构造时只分配了1亿位），【必须提前判断并丢弃，否则越界写入将破坏内存】。

第三步：遍历完成后，bitmap中所有被set过的位对应数值即为去重后的结果集。

这一步无需额外空间存结果，原始数据流式处理，峰值内存=位图大小+单行缓冲区。

高效枚举所有去重值

提供iterator接口：从0开始扫描每个bucket，对每个非零uint32_t，用Brian Kernighan算法逐个提取置位位置——n & (n-1)清除最低位1，配合n & -n定位最低位1的位置。

比暴力遍历32位快得多，尤其当稀疏时（如10亿数中只有100万不重复），时间复杂度趋近于O(去重数量)而非O(总位数)。

每次next()返回下一个去重整数，内部维护当前bucket索引和当前word内偏移，状态轻量。

完整可运行源码集成

定义Bitmap类含私有成员vector bits；公有方法包括构造函数（接受最大值）、set、test、clear、size_in_bits、count_ones（统计已置位数）。

main函数中：从argv[1]读取文件路径→按行读取→strtol转int→过滤负数与超限值→调用set→最后调用count_ones输出去重总数。

编译命令：g++ -std=c++17 -O2 bitmap.cpp -o bitmap；输入文件每行一个十进制整数，支持10^9级别数据量。

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！