一. 位图1.基本了解概念位图Bitmap是一种使用二进制位保存数据状态的数据结构。一个二进制位只有两种状态0和1。因此当我们只需要记录某个数据“存在”或“不存在”时就可以用一个 bit 表示而不必使用完整的整型变量。位图的特点是空间占用小并且插入、删除和查找的效率都非常高。在处理大量整数时位图是一种非常实用的数据结构。先来看一道腾讯、百度等公司曾经考察过的面试题给定40亿个不重复的无符号整数这些整数没有排序。现在再给一个无符号整数如何快速判断这个数是否在这40亿个整数中1.思路一暴力遍历最直接的方法是从头到尾遍历这40亿个整数将每个整数与目标值进行比较。如果找到了目标值就说明目标值存在遍历结束仍然没有找到则说明目标值不存在。这种方法的时间复杂度为O(N)当数据量达到40亿时最坏情况下需要比较40亿次查询效率非常低。因此暴力遍历不能算是一种“快速判断”的方案。2.思路二排序加二分查找另一种思路是先对40亿个整数进行排序然后使用二分查找。排序的时间复杂度大约为O(Nlog N)排序完成后单次二分查找的时间复杂度为O(log N)单看查询效率二分查找已经非常快。但是在采用这种方案之前还需要考虑内存问题。一个无符号整数通常占用4个字节因此40亿个整数需要的存储空间约为40亿*4byte160亿byte16GB所以如果机器没有足够大的内存就无法直接将全部数据加载到内存中进行普通排序。虽然也可以使用外部排序等磁盘处理方案但其实现更加复杂磁盘访问速度也比内存访问慢得多。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查询某个整数时直接检查它对应的 bitbit为1表示存在bit为0表示不存在。构建位图需要遍历一次原始数据时间复杂度为 O(N)。位图构建完成后单次查询的时间复杂度为 O(1)。需要注意位图应该按照整数的取值范围分配空间而不是按照实际的数据数量分配空间。题目中虽然只有40亿个整数但它们可能分布在整个uint32_t的取值范围中所以需要申请 2^32 个 bit而不只是40亿个 bit。2.位图实现位图的本质可以看作一个使用直接定址法实现的哈希表。普通哈希表需要通过哈希函数计算位置并且可能产生哈希冲突。位图则直接使用整数值计算其对应位置不会出现哈希冲突。如何保存二进制位C没有可以直接作为普通容器元素使用的单 bit 类型因此通常使用整型数组保存位图。例如可以使用vectorint作为底层存储。一个int包含32个 bit因此可以表示32个整数的存在状态第0个整数保存整数031的状态第1个整数保存整数3263的状态第2个整数保存整数6495的状态后面的数据依次类推。当需要处理整数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 是否为1return (_bits[i] (1 j)) ! 0;位图类的实现#include vector namespace kong { templatesize_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::vectorint _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::bitset100 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::bitsetINT_MAX因为INT_MAX等于 2^32-1而从0到INT_MAX一共有 (2^32) 个不同的值。对于如此大的位图还需要确保程序运行在64位环境中并且对象通过动态内存保存避免占用过大的栈空间。3. C标准库中的位图bitsetC标准库提供了std::bitset其功能与我们实现的位图类似。使用时需要包含头文件#include bitset例如#include bitset #include iostream int main() { std::bitset100 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将指定位置设置为1bs.set(30);也可以将所有位置设置为1bs.set();2.reset将指定位置设置为0bs.reset(30);也可以将所有位置设置为0bs.reset();3.test检查指定位置是否为1bool 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 为1std::size_t count bs.count();std::bitsetN的大小必须在编译期间确定。如果需要在运行时确定大小就需要自己实现动态位图或者使用其他动态位集合容器。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::bitset100 bs1; std::bitset100 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::bitsetN _bs1; std::bitsetN _bs2; }; }测试代码如下#include iostream void test_twobitset() { bit::twobitset100 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将对应位置设置为1reset将对应位置设置为0test检查对应位置是否为1。位图的插入、删除和查询操作都可以在 O(1) 时间内完成并且比直接保存整数节省大量空间。当一个 bit 无法表示足够多的状态时还可以使用多个位图组合出多位计数器。例如两个 bit 可以表示整数出现0次、1次、2次以及3次以上。因此位图不仅可以解决整数存在性判断问题还可以用于海量整数去重查找集合交集统计有限次数找出只出现一次的整数找出出现次数不超过指定值的整数。理解位图时最关键的是明确两点位图空间由整数的取值范围决定而不是由实际数据数量决定每个整数需要多少个 bit取决于需要表示多少种状态。