【C++补充】第一弹---位图技术揭秘：内存优化与快速访问
✨个人主页： 熬夜学编程的小林
💗系列专栏： 【C语言详解】 【数据结构详解】【C++详解】
目录
1 位图
1.1 位图相关面试题
1. 面试题
给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。（本题为腾讯/百度等公司出过的⼀个⾯试题）
解题思路1：暴力遍历，时间复杂度O(N)，太慢
解题思路2：排序+⼆分查找。时间复杂度消耗 O(N*logN) + O(logN)
深入分析：解题思路2是否可⾏，我们先算算40亿个数据⼤概需要多少内存。
1G = 1024MB = 1024*1024KB = 1024*1024*1024Byte 约等于10亿多Byte
那么40亿个整数约等于16G，说明40亿个数是无法直接放到内存中的，只能放到硬盘文件中。而⼆分查找只能对内存数组中的有序数据进行查找。
解题思路3：数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用⼀个⼆进制比特位来代表数据是否存在的信息，如果⼆进制比特位为1，代表存在，为0代表不存在。那么我们设计⼀个用位表示数据是否存在的数据结构，这个数据结构就叫位图。
比如：
1.2 位图的设计及实现
位图本质是⼀个直接定址法的哈希表，每个整型值映射⼀个bit位，位图提供控制这个bit的相关接⼝。
实现中需要注意的是，C/C++没有对应位的类型，只能看int/char这样整形类型，我们再通过位运算去控制对应的比特位。比如我们数据存到vector<int>中，相当于每个int值映射对应的32个值，比如第⼀个整形映射0-31对应的位，第⼆个整形映射32-63对应的位，后⾯的以此类推，那么来了⼀个整形值x，i = x / 32；j = x % 32；计算出x映射的值在vector的第i个整形数据的第j位。
解决给40亿个不重复的⽆符号整数，查找⼀个数据的问题，我们要给位图开2^32个位，注意不能开40亿个位，因为映射是按大小 映射的，我们要按数据大小范围开空间，范围是是0-2^32-1，所以需要开2^32个位。然后从文件中依次读取每个set到位图中，然后就可以快速判断⼀个值是否在这40亿个数中了。
注意：C++库中的位图不能直接开辟2^32个位的空间，需要通过指针new这么大的空间，代码如下：
#include<iostream> #include<bitset> using namespace std; int main() { // 开2^32个位的位图 //std::bitset<-1> bs1;// C++库开不了这么大空间 //std::bitset<0xffffffff> bs2; // INT_MAX ->2,147,483,647 ->7FFF FFFF // UINT_MAX -> 0xffffffff //std::bitset<UINT_MAX> bs3; std::bitset<-1>* ptr = new std::bitset<-1>();// C++库能够new这么多空间 return 0; }开辟成功
