500MB 搞定 40 亿整数判存！位图 (Bitmap) 的底层实现与海量数据应用

你是否遇到过这样的场景：面对 40 亿个无符号整数，需要快速判断某个数是否存在，但直接存储这些数据需要 16GB 内存，普通电脑根本扛不住？这时候，位图（Bitmap）就能用不到 500MB 的空间解决这个难题 —— 它是海量数据判存场景的 “空间魔术师”，也是 C++ 工程师必须掌握的核心数据结构。

目录

一、为什么需要位图？—— 海量数据的存储困境

1. 常规解法的致命缺陷

2. 位图的核心思想：用 “位” 代替 “字节”

二、位图的底层实现：从原理到代码

1. 核心结构与初始化

2. 核心接口实现：set/reset/test

（1）set：标记数值存在（置 1）

（2）reset：取消数值标记（置 0）

（3）test：判断数值是否存在

3. 关键注意事项

三、位图的实战应用：不止于判存

1. 整型数据排序 + 去重

2. 集合运算（交集 / 并集）

3. 操作系统底层应用

四、位图的局限性与扩展

1. 核心局限

2. 扩展：双位标记法（统计出现次数）

五、完整测试示例

总结

一、为什么需要位图？—— 海量数据的存储困境

先看一个经典面试题：给定 40 亿个不重复的无符号整数（未排序），快速判断某个无符号整数是否存在。

1. 常规解法的致命缺陷

我们先算一笔空间账：

• 无符号整数占 4 字节，40 亿个整数的总空间 = 40 亿 × 4B = 16GB；
• 普通电脑内存通常为 8GB，即便有 16GB，操作系统和其他程序也会占用大量空间，16GB 数据根本无法全部加载到内存。

再看常见解法的问题：

核心矛盾：常规解法的空间复杂度太高，无法适配海量数据的判存需求。

2. 位图的核心思想：用 “位” 代替 “字节”

位图的本质是用一个二进制位表示一个数的存在状态（1 = 存在，0 = 不存在），通过 “直接定址法” 建立数值到二进制位的映射：

• 无符号整数的范围是0∼232−1（约 42 亿），仅需 42 亿个二进制位；
• 空间计算：42 亿 bit = 42 亿 / 8 / 1024 / 1024 ≈ 512MB，相比 16GB 节省 32 倍空间！

这种 “用位代替字节” 的设计，让位图成为海量数据判存的最优解。

二、位图的底层实现：从原理到代码

位图的实现核心是 “位运算”—— 计算机最小存储单位是字节（8 位），我们需要用整型数组（如vector<int>）封装位操作，每个 int 占 32 位，可存储 32 个数值的状态。

1. 核心结构与初始化

先看bitset.h中的核心定义：

namespace sicheng { class bitset { public: // 构造函数：初始化位图空间 bitset(size_t N) { // 关键：N/32+1 避免N<32时空间为0 _bits.resize(N/32+1, 0); _num = 0; // 记录有效数据个数 } private: std::vector<int> _bits; // 存储位数据的整型数组 size_t _num; // 标记的有效数据个数 }; }

关键解读：

• 空间计算：若需要存储 N 个位，需开辟N/32+1个 int（而非直接N/32），避免 N<32 时空间为 0（如 N=30 时，30/32=0，+1 后至少分配 1 个 int）；
• 初始化：resize会将数组初始化为 0，所有位默认表示 “不存在”。

2. 核心接口实现：set/reset/test

位图的核心操作是 “标记存在” “取消标记” “判断存在”，全部通过位运算实现：

（1）set：标记数值存在（置 1）

void set(size_t x) { size_t index = x / 32; // 计算x映射到第几个int size_t pos = x % 32; // 计算x在int中的第几位 _bits[index] |= (1 << pos); // 位或操作：仅将pos位设为1，不影响其他位 _num++; }

原理拆解：

• 例如 x=60：index=60/32=1（第 2 个 int），pos=60%32=28（第 28 位）；
• 1 << pos构造 “仅第 28 位为 1” 的掩码，与_bits[index]做或运算，即可将第 28 位置 1。

（2）reset：取消数值标记（置 0）

void reset(size_t x) { size_t index = x / 32; size_t pos = x % 32; // 位与操作：先取反掩码（仅pos位为0），再与运算将pos位置0 _bits[index] &= ~(1 << pos); _num--; }

原理拆解：

• ~(1 << pos)会生成 “除 pos 位外全为 1” 的掩码；
• 与运算后，只有 pos 位会被置 0，其他位保持不变。

（3）test：判断数值是否存在

bool test(size_t x) { size_t index = x / 32; size_t pos = x % 32; // 与运算：仅保留pos位的值，非0则存在，0则不存在 return _bits[index] & (1 << pos); }

原理拆解：

• 若 pos 位为 1，与运算结果非 0（返回 true）；若为 0，结果为 0（返回 false）；
• 位运算效率极高，时间复杂度为O(1)。

3. 关键注意事项

• 位运算优先级：移位运算（<<）优先级低于取反（~）和加减，必须加括号（如~(1 << pos)而非~1 << pos）；
• 大小端无关：移位操作是逻辑层面的，与内存的大小端存储无关，编译器会自动处理；
• 边界处理：空间计算N/32+1最多浪费 31 个位，现代计算机中可忽略不计（若追求极致空间，可改用vector<char>，计算N/8+1，最多浪费 7 个位）。

三、位图的实战应用：不止于判存

位图的核心优势是 “空间效率” 和 “时间效率”，除了 40 亿整数判存，还有这些经典场景：

1. 整型数据排序 + 去重

• 原理：遍历所有数值，存在的数值标记为 1；再遍历位图，输出所有标记为 1 的位置，自然得到有序且去重的结果；
• 效率：时间复杂度O(n)，空间复杂度仅需位图大小，远优于传统排序算法。

2. 集合运算（交集 / 并集）

• 并集：两个位图的位或运算（bits1 | bits2）；
• 交集：两个位图的位与运算（bits1 & bits2）；
• 差集：位图 1 与位图 2 取反后的位与运算（bits1 & ~bits2）。

3. 操作系统底层应用

• 标记磁盘块的使用状态（已分配 / 空闲）；
• 进程调度中的资源标记（如文件描述符的占用状态）。

四、位图的局限性与扩展

1. 核心局限

• 仅支持整型数据：位图是 “数值→位” 的直接映射，无法直接处理字符串、结构体等非整型数据；
• 空间浪费：若数据稀疏且范围极大（如仅存储 1 和 10 亿两个数），位图仍需开辟 10 亿位空间，造成浪费。

2. 扩展：双位标记法（统计出现次数）

如果需要统计数值出现的次数（如找出只出现一次的数），可将 1 个位扩展为 2 个位：

• 00：未出现；
• 01：出现 1 次；
• 10/11：出现多次；
• 优势：仅需双倍位空间，即可完成海量数据的频次统计，远优于哈希表。

五、完整测试示例

#pragma once #include <vector> namespace sicheng { class bitset { public: bitset(size_t N) { _bits.resize(N/32+1, 0); _num = 0; } void set(size_t x) { size_t index = x / 32; //算出映射的位置再第几个整型 size_t pos = x % 32; //算出x再整形的第几个位 _bits[index] |= (1 << pos); //将第pos个位置成1 表示该位存在x这个数据 _num++; //_bits[index] = _bits[index] |(1 << pos); } void reset(size_t x) { size_t index = x / 32; //算出映射的位置再第几个整型 size_t pos = x % 32; //算出x再整形的第几个位 _bits[index] &= ~(1 << pos); //将第pos给位置成0 _num--; //_bits[index] = _bits[index] & (~(1 << pos)); } //判断x在不在（也即是说x映射的位是否为1） bool test(size_t x) { size_t index = x / 32; //算出映射的位置再第几个整型 size_t pos = x % 32; //算出x再整形的第几个位 //如果该位为1则除该位外都置成0 相反的该位为0则全部置成0 0就是false 非0就是true return _bits[index] & (1 << pos); } private: //int* _bits; std::vector<int> _bits; size_t _num; //映射存储了多少个数据 }; void test_bitset() { bitset bs(100); // 开辟100位空间（4个int） bs.set(98); bs.set(99); bs.set(5); bs.reset(99); // 遍历测试所有位 for (size_t i = 0; i < 100; i++) { printf("[%d]:%d\n", i, bs.test(i)); } } }

输出结果：仅 5 和 98 的位置为 1，99 的位置为 0，其余均为 0。

总结

位图是 “空间换时间” 思想的极致体现，核心要点如下：

1. 核心原理：用二进制位标记数值状态，空间复杂度仅为O(N/8)（N 为数值范围）；
2. 核心操作：通过位运算实现 set/reset/test，时间复杂度均为O(1)；
3. 适用场景：海量整型数据的存在性判断、排序去重、集合运算；
4. 扩展方向：双位标记法可解决频次统计问题，布隆过滤器可解决非整型数据判存问题。

🍍 我是思成！若这篇内容帮你理清了位图的底层实现与海量数据应用逻辑：

👀 【关注】跟我一起拆解数据结构核心知识点，从位图的位运算实现到布隆过滤器扩展，吃透每一个空间优化技巧

❤️ 【点赞】让技术干货被更多人看见，让 40 亿整数判存的内存难题，用 500MB 空间轻松解决

⭐ 【收藏】把位图的 set/reset/test 接口实现、双位标记法存好，海量数据判重 / 排序去重面试时随时查阅

💬 【评论】分享你使用位图处理大规模整型数据时踩过的坑，或想深挖的位图扩展场景，一起交流进步

技术学习没有捷径，但找对思路能少走弯路～愿我们都能把位图的空间压缩思想，转化为可落地的海量数据处理代码，一步步构建高效的算法体系！