文章目录
1. 位图概念2. 位图的实现3. 位图的应用
1. 位图概念
面试题
给 40 亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这 40 亿个数中。
遍历，时间复杂度 O(N)
排序 O(NlogN)，利用二分查找：logN
位图解决：
数据是否在给定的整型数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在，如果二进制比特位为 1，代表存在，为 0 代表不存在。
位图概念
所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。
2. 位图的实现
template<size_t N>class bitset{public:bitset(){_bits.resize(N / 32 + 1, 0);}// 把 x 映射的位标记成 1void set(size_t x){assert(x <= N);size_t i = x / 32;size_t j = x % 32;_bits[i] |= (1 << j);}// 将 x 映射的位标记成 0void reset(size_t x){assert(x <= N);size_t i = x / 32;size_t j = x % 32;_bits[i] &= ~(1 << j);}// 检测位图中 x 是否为 1bool test(size_t x){assert(x <= N);size_t i = x / 32;size_t j = x % 32;return _bits[i] & (1 << j);}private:vector<int> _bits;};3. 位图的应用
快速查找某个数据是否在一个集合中；排序 + 去重；求两个集合的交集、并集等；操作系统中磁盘块标记；…END