一. 位图
1.基本了解
概念：位图（Bitmap）是一种使用二进制位保存数据状态的数据结构。
一个二进制位只有两种状态：0和1。因此，当我们只需要记录某个数据“存在”或“不存在”时，就可以用一个 bit 表示，而不必使用完整的整型变量。
位图的特点是空间占用小，并且插入、删除和查找的效率都非常高。在处理大量整数时，位图是一种非常实用的数据结构。
先来看一道腾讯、百度等公司曾经考察过的面试题：
给定40亿个不重复的无符号整数，这些整数没有排序。现在再给一个无符号整数，如何快速判断这个数是否在这40亿个整数中？
<1>.思路一：暴力遍历
最直接的方法是从头到尾遍历这40亿个整数，将每个整数与目标值进行比较。
如果找到了目标值，就说明目标值存在；遍历结束仍然没有找到，则说明目标值不存在。
这种方法的时间复杂度为：O(N)
当数据量达到40亿时，最坏情况下需要比较40亿次，查询效率非常低。
因此，暴力遍历不能算是一种“快速判断”的方案。
<2>.思路二：排序加二分查找
另一种思路是先对40亿个整数进行排序，然后使用二分查找。
排序的时间复杂度大约为：O(Nlog N)
排序完成后，单次二分查找的时间复杂度为：O(log N)
单看查询效率，二分查找已经非常快。但是在采用这种方案之前，还需要考虑内存问题。
一个无符号整数通常占用4个字节，因此40亿个整数需要的存储空间约为：
40亿*4byte=160亿byte=16GB，所以如果机器没有足够大的内存，就无法直接将全部数据加载到内存中进行普通排序。
虽然也可以使用外部排序等磁盘处理方案，但其实现更加复杂，磁盘访问速度也比内存访问慢得多。
<3>.解题思路三：使用位图
这道题只需要判断一个整数“存在”或者“不存在”，结果刚好只有两种状态：
存在；
不存在。
两种状态正好可以使用一个二进制位表示：
bit为
1，表示整数存在；bit为
0，表示整数不存在。
这就是位图。
32 位无符号整数的取值范围是：0 ～ 2³² − 1，即0 ～ 4,294,967,295。
所以，一共存在 2³²，也就是 4,294,967,296 种不同的取值。
我们可以申请 2³² 个二进制位，让每一个 32 位无符号整数都映射到一个固定的 bit 上。
位图需要的空间为：2³² bit
由于 8 个 bit 等于 1 个字节，因此：2³² ÷ 8 = 2²⁹ Byte = 512 MB
也就是说，只需要 512 MB 的空间，就可以用位图记录所有 32 位无符号整数是否出现过。
也就是说，使用大约512 MB的内存，就可以记录整个32位无符号整数范围中每一个整数是否存在。
处理过程如下：
创建包含 2^32 个 bit 的位图；
从文件中依次读取40亿个整数；
将每个整数对应的 bit 设置为
1；查询某个整数时，直接检查它对应的 bit；
bit为
1表示存在，bit为0表示不存在。
构建位图需要遍历一次原始数据，时间复杂度为 O(N)。位图构建完成后，单次查询的时间复杂度为 O(1)。
需要注意，位图应该按照整数的取值范围分配空间，而不是按照实际的数据数量分配空间。
题目中虽然只有40亿个整数，但它们可能分布在整个uint32_t的取值范围中，所以需要申请 2^32 个 bit，而不只是40亿个 bit。
2.位图实现
位图的本质可以看作一个使用直接定址法实现的哈希表。
普通哈希表需要通过哈希函数计算位置，并且可能产生哈希冲突。位图则直接使用整数值计算其对应位置，不会出现哈希冲突。
如何保存二进制位？
C++没有可以直接作为普通容器元素使用的单 bit 类型，因此通常使用整型数组保存位图。
例如，可以使用vector<int>作为底层存储。一个int包含32个 bit，因此可以表示32个整数的存在状态：
第0个整数保存整数0～31的状态；
第1个整数保存整数32～63的状态；
第2个整数保存整数64～95的状态；
后面的数据依次类推。
当需要处理整数x时，可以通过下面的方式计算它所在的位置：
size_t i = x / 32; size_t j = x % 32;其中：
i表示x位于数组中的第几个整数；j表示x位于这个整数的第几个 bit。
由于32是2的幂，也可以使用位运算：
size_t i = x >> 5; size_t j = x & 31;设置一个 bit，将整数x对应的 bit 设置为1：
_bits[i] |= (1 << j);<1>.清除一个 bit
将整数x对应的 bit 设置为0：
_bits[i] &= ~(1 << j);<2>.检查一个 bit
判断整数x对应的 bit 是否为1：
return (_bits[i] & (1 << j)) != 0;位图类的实现：
#include <vector> namespace kong { template<size_t N> class bit_set { public: bit_set() { _bs.resize(N / 32 + 1); } void set(size_t x) { int i = x / 32; int j = x % 32; _bs[i] |= (1 << j); } void reset(size_t x) { int i = x / 32; int j = x % 32; _bs[i] &= (~(1 << j)); } bool test(size_t x) { int i = x / 32; int j = x % 32; return _bs[i] & (1 << j); } private: std::vector<int> _bs; }; }这里使用：
(N + 31) / 32计算需要多少个uint32_t，其作用是向上取整。
例如：
需要32个 bit时，申请1个int；
需要33个 bit时，申请2个 int；
需要64个 bit时，申请2个 int。
测试代码：
#include "Bit_set.h" int main() { bit::bitset<100> bs; bs.set(50); bs.set(30); bs.set(90); for (std::size_t i = 0; i < 100; ++i) { if (bs.test(i)) { std::cout << i << " -> 在\n"; } else { std::cout << i << " -> 不在\n"; } } bs.reset(90); bs.set(91); std::cout << '\n'; for (std::size_t i = 0; i < 100; ++i) { if (bs.test(i)) { std::cout << i << " -> 在\n"; } else { std::cout << i << " -> 不在\n"; } } return 0; }第一次设置了：
30、50、90所以这三个整数对应的位置为1。
随后执行：
bs.reset(90); bs.set(91);整数90对应的位置被清零，整数91对应的位置被设置为1。
如何申请 2^32 个 bit
如果要覆盖整个32位无符号整数范围，需要的 bit 数量是：
1 << 32不能直接写成：
bit::bitset<INT_MAX>因为INT_MAX等于 2^32-1，而从0到INT_MAX一共有 (2^32) 个不同的值。
对于如此大的位图，还需要确保程序运行在64位环境中，并且对象通过动态内存保存，避免占用过大的栈空间。
3. C++标准库中的位图bitset
C++标准库提供了std::bitset，其功能与我们实现的位图类似。
使用时需要包含头文件：
#include <bitset>例如：
#include <bitset> #include <iostream> int main() { std::bitset<100> bs; bs.set(30); bs.set(50); bs.set(90); std::cout << bs.test(30) << '\n'; std::cout << bs.test(40) << '\n'; bs.reset(30); std::cout << bs.test(30) << '\n'; return 0; }std::bitset的核心接口包括：
<1>.set
将指定位置设置为1：
bs.set(30);也可以将所有位置设置为1：
bs.set();<2>.reset
将指定位置设置为0：
bs.reset(30);也可以将所有位置设置为0：
bs.reset();<3>.test
检查指定位置是否为1：
bool exists = bs.test(30);<4>.operator[]
像访问数组一样访问某个位置：
bs[30] = 1; if (bs[30]) { std::cout << "30对应的位置为1\n"; }<5>.to_string
将位图转换成由0和1组成的字符串：
std::string result = bs.to_string();<6>.count
统计位图中有多少个 bit 为1：
std::size_t count = bs.count();std::bitset<N>的大小必须在编译期间确定。如果需要在运行时确定大小，就需要自己实现动态位图，或者使用其他动态位集合容器。
4. 位图的优缺点
4.1.位图的优点
<1>. 节省空间
普通32位整数需要4个字节，而位图只需要一个 bit 表示某个整数是否存在。
在只需要记录“存在或不存在”的场景下，位图可以显著降低内存占用。
<2>. 增删查改速度快
整数可以直接映射到固定的 bit，因此：
插入一个整数，就是将对应 bit 设置为
1；删除一个整数，就是将对应 bit 设置为
0；查询一个整数，就是检查对应 bit；
修改状态，就是对对应 bit 进行位运算。
这些操作的时间复杂度都是 (O(1))。
<3>. 不存在哈希冲突
位图采用直接映射，每个整数都有唯一的位置，不需要解决普通哈希表中的哈希冲突问题。
4.2.位图的缺点
<1>. 主要适用于整数
位图使用整数值计算位置，因此天然适用于整型数据。
如果需要处理字符串、对象等数据，就必须先把它们映射为整数。
<2>. 空间大小取决于数据范围
位图占用的空间不是由实际数据数量决定的，而是由数据的最大取值范围决定的。
如果数据量很少，但最大值特别大，使用位图就可能浪费大量空间。
例如，只有两个整数：
1和1000000000如果直接使用位图，就需要为0到10亿的范围分配空间。
<3>. 普通位图只能表示两种状态
一个 bit 只能表示0和1，因此普通位图只能记录数据是否存在。
如果需要记录出现次数，就必须使用多个 bit 表示一个整数的状态。
5. 位图相关问题
5.1.找出只出现一次的整数
给定100亿个整数，设计算法找出只出现一次的整数。
普通位图只能表示：
0：没有出现；1：出现过。
它不能区分一个整数究竟出现了一次还是多次。
因此，可以使用两个位图，让每个整数拥有两个状态位：
| 状态 | 出现次数 |
|---|---|
00 | 出现0次 |
01 | 出现1次 |
10 | 出现2次 |
11 | 出现3次及以上 |
每读取到一次整数，就更新它的状态：
00 → 01 01 → 10 10 → 11 11 → 11读取完所有数据后，遍历全部状态，输出状态为01的整数，这些整数就是只出现一次的整数。
5.2.求两个文件中整数的交集
给定两个文件，每个文件分别包含100亿个整数，只有1G左右的内存，如何找到两个文件的交集？
可以使用位图记录两个文件中的数据。
基本思路是：
将第一个文件中的整数写入第一个位图；
将第二个文件中的整数写入第二个位图；
遍历整数取值范围；
如果某个整数在两个位图中都存在，它就是交集元素。
下面使用较小的数据范围模拟求交集：
#include <bitset> #include <iostream> void test_bitset_intersection() { int a1[] ={5, 7, 9, 2, 5, 99, 5, 5,7, 5, 3, 9, 2, 55, 1, 5, 6}; int a2[] ={5, 3, 5, 99, 6, 99, 33, 66}; std::bitset<100> bs1; std::bitset<100> bs2; for (int value : a1) { bs1.set(value); } for (int value : a2) { bs2.set(value); } for (std::size_t i = 0; i < 100; ++i) { if (bs1.test(i) && bs2.test(i)) { std::cout << i << '\n'; } } }输出结果为：
3 5 6 99这些整数同时出现在两个数组中，因此属于交集。
在实际处理完整uint32_t范围时，一个位图约占512 MiB，两个位图约占1 GiB。若内存限制非常严格，也可以只为第一个文件创建位图，然后逐个读取第二个文件并进行判断。
5.3.找出出现次数不超过两次的整数
一个文件中有100亿个整数，给定1G左右的内存，设计算法找出出现次数不超过两次的所有整数。
仍然可以使用两个 bit 记录一个整数的出现次数：
| 状态 | 含义 |
00 | 没有出现 |
01 | 出现1次 |
10 | 出现2次 |
11 | 出现3次及以上 |
最后遍历整个状态表，输出状态为01和10的整数。
这里的“不超过两次”通常指文件中实际出现过一次或两次的整数，因此不输出状态为00的整数。
5.4.两位计数位图的实现
#include <bitset> #include <cstddef> namespace bit { template <std::size_t N> class twobitset { public: void set(std::size_t x) { bool bit1 = _bs1.test(x); bool bit2 = _bs2.test(x); if (!bit1 && !bit2) { // 00 → 01 _bs2.set(x); } else if (!bit1 && bit2) { // 01 → 10 _bs1.set(x); _bs2.reset(x); } else if (bit1 && !bit2) { // 10 → 11 _bs1.set(x); _bs2.set(x); } // 已经是11时继续保持11 } // 返回0：出现0次 // 返回1：出现1次 // 返回2：出现2次 // 返回3：出现3次及以上 int get_count(std::size_t x) const { bool bit1 = _bs1.test(x); bool bit2 = _bs2.test(x); if (!bit1 && !bit2) { return 0; } else if (!bit1 && bit2) { return 1; } else if (bit1 && !bit2) { return 2; } else { return 3; } } private: std::bitset<N> _bs1; std::bitset<N> _bs2; }; }测试代码如下：
#include <iostream> void test_twobitset() { bit::twobitset<100> tbs; int values[] ={5, 7, 9, 2, 5, 99, 5, 5,7, 5, 3, 9, 2, 55, 1, 5,6, 6, 6, 6, 7, 9}; for (int value : values) { tbs.set(value); } for (std::size_t i = 0; i < 100; ++i) { int count = tbs.get_count(i); if (count == 1 || count == 2) { std::cout << i << '\n'; } } }在这个例子中：
状态为
01的整数出现了一次；状态为
10的整数出现了两次；状态为
11的整数出现了三次及以上，不会被输出。
需要说明的是，两个完整的32位无符号整数位图大约需要1 GiB内存。如果题目中的“1G内存”是严格限制，还需要考虑程序、容器及输入输出缓冲区的额外内存占用。
6.总结
位图使用一个二进制位表示一个整数的存在状态，是处理海量整数问题时非常重要的数据结构。
对于完整的32位无符号整数范围：0 ～ 2³² − 1，即0 ～ 4,294,967,295。
普通位图提供三个核心操作：
set：将对应位置设置为1；reset：将对应位置设置为0；test：检查对应位置是否为1。
位图的插入、删除和查询操作都可以在 O(1) 时间内完成，并且比直接保存整数节省大量空间。
当一个 bit 无法表示足够多的状态时，还可以使用多个位图组合出多位计数器。例如，两个 bit 可以表示整数出现0次、1次、2次以及3次以上。
因此，位图不仅可以解决整数存在性判断问题，还可以用于：
海量整数去重；
查找集合交集；
统计有限次数；
找出只出现一次的整数；
找出出现次数不超过指定值的整数。
理解位图时，最关键的是明确两点：
位图空间由整数的取值范围决定，而不是由实际数据数量决定；
每个整数需要多少个 bit，取决于需要表示多少种状态。