1.位图
【题目】
给 40 亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这 40 亿个数中。
【常规思路及其问题】
遍历 40 亿个数，时间复杂度为 O(N)。但每次查询都要把约 16 GB 的数据读一遍，只适合查询次数极少的场景。
先排序，快排平均 O(N log N)，再利用二分查找 O(log N)。但快排需要随机访问，得把 16 GB 数据全部载入内存才快；内存不够时只能做外排序，而磁盘上的二分代价很高（见下文（b））。
把数据放进 set / unordered_set 中，再查找 key 在不在。set 底层是红黑树，unordered_set 是哈希表，除了 4 字节的数据本身，每个元素还要额外保存指针、颜色、桶等控制信息，40 亿元素需要的内存比 16 GB 还大得多。
先算一下 40 亿个整数要占用多少空间：
1 GiB = 1024 × 1024 × 1024 = 2^30 字节 ≈ 10.7 亿字节
4 GiB = 4 × 2^30 = 2^32 字节 ≈ 42.9 亿字节
40 亿个 unsigned int = 40 亿 × 4 字节 = 160 亿字节 = 16.0 GB（约合 14.9 GiB）
上面三种解法看似可行，实际上都有很大的问题：内存消耗太大。
（a）难道在内存中开一个 16 GB 空间的数组存放这些数据吗？前提是机器有这么多内存。很多机器只有 4 GB / 8 GB 内存，显然不太现实，内存消耗太大了。
（b）虽然归并排序可以对文件中的数据做外排序，但是效率很低：磁盘读写速度慢；而且排序完成后想在磁盘上二分查找，虽然每条记录定长 4 字节、下标可以算出来（第 i 条记录在 i × 4 处），但一次二分大约需要 32 次随机磁盘 I/O，只查一两个数很不划算。要在实际工程中用，还得额外建稀疏索引来减少随机 I/O。
（c）把数据放进 set / unordered_set 中，因为 set 底层是红黑树、unordered_set 是哈希桶加链表，除了存数据本身，还要存指针等附加信息，内存消耗比 16 GB 还大很多，更不可行。
所以一定要从节省内存的角度出发去思考，才能更好地解决问题。同时题目要求是：快速判断。
这里是判断一个数在不在数据集中，仔细想一想，也并不需要把这个数存起来，只需要有个标记去标记某个数在不在就行了。（好比统计数组中数字的出现次数，我们用数值作下标，在该下标处存储出现次数，也并没有把数存下来。）标记一个数在不在，逻辑上只需要一个比特位（0 / 1）就能表示，用一个比特位标记一个数，空间就省下来了。
【位图：到底省多少空间】
无符号整数是 32 位，值域是 [0, 2^32)。用 1 bit 表示一个数是否存在，就得到一张 2^32 位的表：2^32 bit = 2^29 字节 = 512 MiB
也就是说，16 GB 的数据，用 512 MiB 的位图就能表示每个数在不在。内存降到约 1/30，建表时间 O(N)，查询一次 O(1)。
40 亿 / 42.9 亿 ≈ 93%，本题的数据几乎填满整个值域，属于位图最理想的场景。
【适用条件】
- 值域小且数据稠密 --> 位图最优，本题正是这种场景；
- 值域大且稀疏（如 64 位整数）--> 位图不可行，改用哈希表或布隆过滤器（有误判、不支持删除）；
- 需要统计出现次数 --> 用 2-bit 位图（0 / 1 / 多次）；
- 内存不足 512 MiB --> 按值域分段、多趟扫描，用时间换空间。
这里我们将采用第四种解法：位图。
某个数是否在给定的数据集中，有两种结果：存在 / 不存在，刚好是两种状态，那么可以使用一个二进制比特位来代表某个数是否存在的信息，比如比特位为 1 代表存在，为 0 代表不存在。
我们把数据集的所有数用直接定址法映射到一张二进制位表中，并用二进制值（1 / 0）标记其是否存在。这样每个数都有唯一的映射位置，不会出现哈希冲突。如果要判断某个数在不在数据集中，只需要找到这个数映射到表中的位置，然后查看该位置的比特位是 1 还是 0。
我们是用每个无符号整数 unsigned int 的值来映射其位置（比如 25，就映射到第 25 个二进制位）：因为 unsigned int 的取值范围是 0 ~ 2^32 - 1，所以一个无符号整数最小值为 0，最大值为 2^32 - 1（4,294,967,295，约 42.9 亿）。
要映射完所有无符号整数，表需要有 2^32 个二进制位（下标 0 ~ 2^32 - 1），即：2^32 bit = 2^32 / 8 字节 = 2^29 字节 = 536,870,912 字节 ≈ 5.37 亿字节 = 512 MiB（约 0.5 GiB）
一个 bit 位标记一个 unsigned int 值，512 MiB 的内存就可以标记完 42.9 亿个整数的存在状态；相比把 40 亿个数直接存下来需要的约 16 GB，内存降到约 1/30，极大节省了内存。
注意：位图并没有把整个数据集存储起来，而是将所有数映射到一张连续的二进制位表（本质是直接定址的位数组）中，在映射的位置上标记这个数在不在。
（1）位图概念
面对判断一个数在不在海量数据中的问题，红黑树和哈希表查找效率是挺高的，但是我们光把海量数据存起来够呛，同时红黑树和哈希表附带的内存消耗，所需空间更大，基于这样的原因，提出了位图这种数据结构。
所谓位图（bitset），就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。在索引、数据压缩方面有很大的应用。
template <size_t N> class bitset;
我们要知道，位图是用数组实现的，数组的每一个元素的每一个二进制位都表示一个数据，0 表示该数据不存在，1 表示该数据存在。
位图最大的特点就是：快、节省空间，因为它不需要存储数据集，只是标记某个数在不在这个数据集中。
（2）位图的实现
a. 位图的底层结构
如下图，我们开一个数组，数组的每个元素是一个 char（8个 bit 位）。如果是一个 int （32 个 bit 位）也可以，只是计算数据映射的比特位的方法略有差别。这里的 0 ~ 7 是比特位的编号，从右到左依次编号。
问：如何计算数据 x 映射在数组的第几个字节、第几个比特位上？
以 unsigned char 数组为例（一个 char = 1 字节 = 8 bit）：
- 字节下标 =
x / 8，得出 x 映射在下标为几的 char 中（每个 char 能标记 8 个数）- 位下标 =
x % 8，得出 x 映射在该 char 中的第几个比特位上
注意：这两个都是下标，从 0 开始数。因为 8 是 2 的幂，也可以写成位运算——x >> 3 和 x & 7，编译器会自动优化，比除法取模更快。
比如数据 x = 10，则：
- 字节下标 =
10 / 8 = 1，说明 10 映射在下标为 1 的 char 中（从 0 开始数，是第 2 个字节）- 位下标 =
10 % 8 = 2，说明 10 映射在该字节中下标为 2 的比特位（从 0 开始数，是第 3 个 bit，从最低位 LSB 开始数）- 对应写法：
arr[1] |= (1 << 2);，即把第 1 个字节的 bit 2 置 1
注意：如果数组的每个元素是一个 int，由于 int 通常占 4 字节 = 32 bit，把上面的 8 换成 32 就行：
- 元素下标 =
x / 32，即x >> 5- 位下标 =
x % 32，即x & 31- 置位写法：
arr[x >> 5] |= (1U << (x & 31));
更通用地，设元素占 B 个字节（即 B × 8 个 bit）：
元素下标 = x / (B * 8)
位下标 = x % (B * 8)
补充：
a.1U：无符号整数字面量
U（或 u）是 unsigned 后缀，意思是这个常量按 unsigned int 类型处理，而不是 int。
1 // int 有符号
1U // unsigned int 无符号
1ULL // unsigned long long（64 位）
为什么位图代码里要写 1U：
arr[x >> 5] |= (1U << (x & 31)); // x&31 的范围是 0~31
- 如果写
1 << 31：1是有符号 int，把 1 左移 31 位会移到符号位，C++11 里这是未定义行为（UB），结果不可靠；- 写
1U << 31：无符号数，1U << 31 = 0x80000000，合法且结果确定；- 而且目标数组是
unsigned char/uint32_t时，无符号不会出现符号扩展的坑。
同理，64 位位图要用 1ULL << 63，别用 1 << 63。
2. LSB：最低有效位（Least Significant Bit）
一个字节有 8 个 bit，bit 0 是 LSB（最低位，权值 1），bit 7 是 MSB（最高位，权值 128）：
bit 序号: 7 6 5 4 3 2 1 0
权值: 128 64 32 16 8 4 2 1
MSB LSB
比如字节 0b10110110：
bit7=1 bit6=0 bit5=1 bit4=1 bit3=0 bit2=1 bit1=1 bit0=0
128 - 32 16 - 4 2 -
3. 和位图代码的关系
arr[i] |= (1 << (x % 8));
- 当
x % 8 == 0时，1 << 0 = 0b00000001→ 标记的是 LSB（第 0 位）- 当
x % 8 == 7时，1 << 7 = 0b10000000→ 标记的是 MSB（第 7 位）
所以位下标 = x % 8，从 LSB 开始数.就是这个意思：下标 0 对应二进制最右边的 bit。
同一份代码里，置位和查位必须用同一个方向（都从 LSB 数），不然会标在一个地方、查在另一个地方。
// 位图的结构
namespace hjq
{
template<size_t N> // N: 非类型模板参数，表示至少需要开N个比特位的存储空间
class bitset
{
public:
// 构造有N个比特位的位图，等价于要开N/8个字节(char)的空间
// 为了防止N不是8的整数倍，所以要+1，多开1个字节(char)的空间
bitset() { _bits.resize(N / 8 + 1, 0); }
// 把数据x映射的比特位设置成1，表示数据x存在
void set(size_t x);
// 把数据x映射的比特位设置成0，表示数据x不存在
void reset(size_t x);
// 检测数据x映射的比特位是否为1（即数据x是否存在）
bool test(size_t x) const;
private:
vector<char> _bits; // 位数组
};
}
b. 位图的一些成员函数
① 位图的构造
默认构造：构造至少有 N 个比特位的位图，等价于开 ⌈N / 8⌉ 个字节（char）的空间。
因为 N 不一定是 8 的整数倍，所以向上取整：
explicit BitSet()
{
_bits.resize((N + 7) / 8, 0); // 精确向上取整，不浪费字节
}
说明：
- 若写成
N / 8 + 1，N 正好是 8 的倍数时会多开 1 个字节；(N + 7) / 8才是严格正确且不浪费的写法；_bits用std::vector<unsigned char>，不要用有符号char，避免置位、取反时的符号扩展问题；- 类名用
BitSet而不是bitset，避免和std::bitset重名冲突。
② 位图的插入：set
set 函数：把数据 x 映射的比特位设置成 1。位位置从最右边的位开始计数，即从 0 位置（LSB）开始计数。
// 把数据 x 映射的比特位设置成 1，表示数据 x 存在
void set(size_t x)
{
size_t i = x >> 3; // 等价于 x / 8：x 映射在第 i 个 char（字节）中
size_t j = x & 7; // 等价于 x % 8：x 映射在该字节的第 j 个比特位上
// 把第 i 个 char 的第 j 位置 1，其它位不受影响
_bits[i] |= (1u << j);
}
分析：比如数据 5 映射在第 0 个 char 的第 5 个比特位，i = 5>>3 = 0，j = 5&7 = 5：
0000 1111 -> _bits[0] // 原来的值
| 0010 0000 -> 1u << 5
-----------------------
0010 1111 -> _bits[0] // 第 0 个 char 的第 5 位被置 1
③ 位图的删除：reset
reset 函数：把数据 x 映射的比特位设置成 0。
// 把数据 x 映射的比特位设置成 0，表示数据 x 不存在
void reset(size_t x)
{
size_t i = x >> 3;
size_t j = x & 7;
// 把第 i 个 char 的第 j 位置 0，其它位不变
_bits[i] &= ~(1u << j);
}
注意不能用异或：
_bits[i] ^= (1u << j); // 错！该位本来就是 0 时会被异或成 1
异或是翻转，不是「清零」。示例（x = 5）：
0010 1111 -> _bits[0]
& 1101 1111 -> ~(1u << 5)
-----------------------
0000 1111 -> _bits[0] // 第 5 位被清 0
④ 位图的查找：test
// 检测数据 x 映射的比特位是否为 1：是 1 返回 true，是 0 返回 false
bool test(size_t x) const
{
size_t i = x >> 3;
size_t j = x & 7;
return (_bits[i] & (1u << j)) != 0;
}
示例（x = 5，_bits[0] 当前为 0000 1111，第 5 位是 0）：
0000 1111 -> _bits[0]
& 0010 0000 -> 1u << 5
-----------------------
0000 0000 -> 结果为 0，说明数据 5 不存在
c. 如何开出 42 亿 9 千多万个比特位的位图？
要映射全部 32 位无符号整数（0 ~ 2^32-1），需要 2^32 个比特位：
void test_bitset()
{
// 方式一：语义最清楚，明确要 2^32 个比特位（推荐）
BitSet<(size_t)1 << 32> bs1;
// 方式二：0xffffffff = 2^32-1 个比特位，按字节取整后同样覆盖全部值
BitSet<0xffffffff> bs2;
}
两种写法都占 512 MiB。其中方式二能覆盖全部值的原因：0xffffffff 请求的是 2^32-1 个 bit，但构造时 (N + 7) / 8 会向上取整到字节边界，实际得到 2^32 个 bit，正好对应下标 0 ~ 2^32-1。
错误写法：
BitSet<-1> bs;
-1 传给模板参数 size_t 会按无符号转换：
- 64 位平台（Ubuntu 22.04）：
-1=SIZE_MAX=2^64-1，(N+7)/8≈ 2^61 字节（约 2 EiB），直接std::bad_alloc；- 32 位平台：
size_t只有 4 字节，-1恰好等于0xffffffff，所以有的老教程里"能跑"——这是平台巧合，不能照抄。
（3）位图的应用
快速判断某个数据是否在一个集合中：本文的 40 亿整数判重、黑名单/白名单、URL 去重、大文件的重复数据检测等。前提是数据能映射成整数下标，且值域可控。
排序 + 去重：位图的下标天然有序，遍历输出所有置位下标就是升序结果；重复数据只会占同一个 bit，顺带完成去重。经典题：内存有限时给 1000 万个不重复整数排序。局限是只适合整数（或可一一映射到整数的数据），且不能保留出现次数。
求两个集合的交集、并集、差集：两个位图按位 AND / OR / AND-NOT / XOR，就能得到交集、并集、差集、对称差。典型场景：共同好友、标签/人群圈选、权限合并。
操作系统中磁盘块标记：文件系统用块位图（block bitmap）标记每个磁盘块是否空闲，用inode 位图标记 inode 是否被占用，ext2/3/4、NTFS 等都用这种思路；同理还有物理页（页框）分配位图、进程/线程 ID 分配位图、
fd_set文件描述符集合等——资源数量有限且编号连续，1 bit 表示占用/空闲最省。
2.位图应用（只能处理整数）
（1）给定 100 亿个整数，设计算法 找到只出现一次的整数？
错误思路：
显然不能把这 100 亿个整数存进 map / unordered_map（红黑树 / 哈希表）中。100 亿 × 4 字节 = 40 GB 只是数据本身，map 每个节点还要额外存左右孩子、父指针、颜色，unordered_map 还有桶数组和链表指针，实际内存要几百 GB，完全不现实。
正确思路：
我们需要标记 3 种状态：不存在 / 出现一次 / 出现多次，也就是说要用两个比特位来标记。两个比特位有 4 种表现形式 00 / 01 / 10 / 11：
- 00：这个数不存在
- 01：这个数只出现一次
- 10：这个数出现多次
- 11：（保留，也可以合并表示出现多次）
然后遍历位图，找到所有标记为 01 的位置，该位置映射的就是只出现一次的整数。
问：那这里需要消耗多少空间呢？
要注意：虽然有 100 亿个整数，但并不是开 100 亿个比特位的表。表的长度取决于值域，不是数据量。这 100 亿个 unsigned int 的取值范围都是 0 ~ 2^32-1（约 42.9 亿个整数）：
- 每个整数映射 1 个比特位：2^32 bit = 2^29 字节 = 536,870,912 字节 = 512 MiB（0.5 GiB）
- 每个整数映射 2 个比特位：2 × 2^32 bit = 2^33 bit = 1 GiB
所以 2-bit 位图只要 1 GiB，就能处理 100 亿个整数。
具体做法：
方法一：用一个位图，用 2 个连续的比特位标识一个数。需要修改 2 个不同位置的比特位的值，不方便。
方法二：封装两个位图，用两个位图的同一个位置的 2 个比特位来标识一个数。
所以修改两个位图的同一个位置的比特位的值就好了，还可以复用之前写的位图代码。
我们来看代码实现：
封装了两个位图，找只出现一次的整数N：非类型模板参数，表示至少要开 N 个比特位的存储空间。
template<size_t N>
class FindOnceValSet
{
public:
void set(size_t x) // 把数据 x 映射的比特位设置成 01，表示数据 x 出现一次
{
bool flag1 = _bs1.test(x); // 检测数据 x 在第1个位图中映射的比特位是否为 1
bool flag2 = _bs2.test(x); // 检测数据 x 在第2个位图中映射的比特位是否为 1
// 两个比特位分别为 00，说明数据 x 之前不存在
if (flag1 == false && flag2 == false)
{
// 00 -> 01，标识成出现一次
_bs2.set(x);
}
// 两个比特位分别为 01，说明数据 x 之前已经出现一次
else if (flag1 == false && flag2 == true)
{
// 01 -> 10，标识成出现多次
_bs1.set(x); // 1
_bs2.reset(x); // 0
}
// 两个比特位分别为 10，说明数据 x 之前已经出现多次了，不用处理
// 10 -> 10
}
void print_once_num() // 输出所有只出现一次的数据
{
// 遍历位图中的 N 个比特位
for (size_t i = 0; i < N; i++)
{
// 检测两个位图的同一个位置的比特位是否分别为 0、1
if (_bs1.test(i) == false && _bs2.test(i) == true)
{
cout << i << endl; // 输出此位置映射的数据 i
}
}
}
private:
bitset<N> _bs1; // 位图1
bitset<N> _bs2; // 位图2
};
void testFindOnceValSet()
{
int a[] = { 1,20,23,23,20,5,20,7,3,7 }; // 测试数据
FindOnceValSet<100> bs; // 开至少有100个比特位的位数组
for (const auto& e : a)
{
bs.set(e); // 把数组a的每个元素的出现次数映射到位图bs中
}
bs.print_once_num(); // 输出所有只出现一次的数据
}
运行结果：
1
3
5
（2）给两个文件，分别有 100 亿个整数，我们只有 1G 内存，如何找到两个文件交集？
分析问题：找到两个文件的交集，只需要判断这个数是否分别在两个文件中，是一个典型的 key 模型。解决思路：定义两个位图。
- 位图 1 标识第一个文件中所有数的存在状态（1 存在、0 不存在）。
- 位图 2 标识第二个文件中所有数的存在状态（1 存在、0 不存在）。
- 遍历位图中的 N 个比特位，检测两个位图的同一个位置的比特位的值是否都为 1，如果都为 1，说明此位置映射的这个数就是交集。
我们看一下这里需要消耗的内存：
因为 unsigned int 整数的取值范围是 0 ~ 2³²-1（大约是42亿9千多万个整数），每个整数映射一个比特位，需要消耗 ( 2³²-1 ) / 8 个字节 ≈ 5亿多个字节 ≈ 0.5GB 的空间，这里开了两个位图，需要消耗 1GB 的空间。
#include <iostream>
#include <vector>
#include <cstdint>
using namespace std;
template<size_t N>
class BitSet
{
public:
BitSet() { _bits.resize((N + 7) / 8, 0); } // 向上取整，按字节开空间
void set(size_t x) // 把 x 映射的比特位置 1
{
size_t i = x >> 3; // 等价于 x / 8
size_t j = x & 7; // 等价于 x % 8
_bits[i] |= (1u << j);
}
void reset(size_t x) // 把 x 映射的比特位置 0
{
size_t i = x >> 3;
size_t j = x & 7;
_bits[i] &= ~(1u << j);
}
bool test(size_t x) const // 检测 x 是否存在
{
size_t i = x >> 3;
size_t j = x & 7;
return (_bits[i] & (1u << j)) != 0;
}
private:
vector<unsigned char> _bits; // 用无符号 char，避免符号问题
};
// 遍历 N 个位置，两个位图同一位置都为 1 的就是交集
template<size_t N>
void intersect(const BitSet<N>& bs1, const BitSet<N>& bs2)
{
for (size_t i = 0; i < N; ++i)
{
if (bs1.test(i) && bs2.test(i))
{
cout << i << endl;
}
}
}
void test_intersect()
{
BitSet<100> bs1; // 文件 1 的位图
BitSet<100> bs2; // 文件 2 的位图
int a[] = { 1, 20, 23, 5, 7, 3, 9, 15 };
int b[] = { 3, 20, 8, 9, 30, 1, 45 };
for (int x : a) bs1.set(x); // 模拟读文件 1
for (int x : b) bs2.set(x); // 模拟读文件 2
intersect(bs1, bs2); // 输出交集
}
int main()
{
test_intersect();
return 0;
}
运行结果：
1
3
9
20
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/2501_93351213/article/details/168342243
