位图
1. 位图概念
位图（Bitset）是一种数据结构，用于表示一组布尔值，其中每个元素通常对应于一个位或一个二进制值，可以存储0或1。位图在计算机科学和计算机工程中经常用于各种应用，特别是在位级别的标志、掩码和快速查找中。以下是位图的一些关键特点：
- 二进制表示：位图中的每个元素都只能存储两个值，通常是0和1。这使得位图非常高效，因为每个位只需要一个二进制位来表示。
- 位操作：位图支持各种位操作，包括设置位、清除位、翻转位和查询特定位的操作。
- 空间效率：位图在表示大量布尔值时非常节省内存，因为每个位只需要一个二进制位。这使得位图在大规模数据处理中非常有用。
- 快速查找：位图用于快速查找元素的存在或不存在。通过检查位的值，可以快速确定元素是否在集合中。
- 位运算：位图支持位级别的位运算，如与、或、异或等，这些运算可用于合并和操作多个位图。
应用领域包括：
- 位掩码：用于将一组标志或选项组合在一起，并进行快速检查和设置。
- 布尔向量：用于高效存储和操作布尔值集合。
- 集合操作：用于执行集合操作，如并集、交集和差集。
- 压缩和编码：用于压缩数据，如运行长度编码（Run-Length Encoding）等。
2. 位图在实际中的应用
某大厂给过这样一道面试题，具体如下：
给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中
你可能最开始想遍历？那肯定是不行的，因为40亿个无符号数占用将近15G内存。
那使用散列表呢？那这里使用的空间能在内存上吗？显然不可以，就算可以
- 散列表需要大量内存，因为需要为40亿个整数维护哈希表。
- 哈希冲突可能会导致性能下降，需要解决冲突。
- 需要选择合适的哈希函数以避免碰撞。
又会遇到各种各样的问题
那么这里就可以用到我们上面提到的位图概念
位图（Bitset）方法：
- 创建位图：首先，创建一个足够大的位图，以能够表示您的整数范围。例如，如果整数范围在0到4,000,000,000之间，可以创建一个长度为4,000,000,001的位图。
- 插入数据：将这40亿个无符号整数中的每个整数映射到位图的相应位置，并将对应的位设置为1。
- 查询数据：当需要判断一个数是否在这40亿个数中时，只需查看位图中相应位置的位。如果该位为1，表示该整数在集合中；如果该位为0，表示不在集合中。
优点：
- 位图非常节省内存，因为每个整数只需要一个位。
- 不需要哈希函数，也不需要解决哈希冲突。
这里我们只需要不到500M就很好的解决了这个问题，听起来挺理想的，那么应该如何来实现它呢？
代码如下：
template<size_t N> class bitset { public: bitset() { _bits.resize(N/8+1, 0); } void set(size_t x) { size_t i = x / 8; size_t j = x % 8; _bits[i] |= (1 << j); } void reset(size_t x) { size_t i = x / 8; size_t j = x % 8; _bits[i] &= ~(1 << j); } bool test(size_t x) { size_t i = x / 8; size_t j = x % 8; return _bits[i] & (1 << j); } private: vector<char> _bits; };
模板的作用就是用来传需要查询数的范围，比如我们这里有40亿怎么传值呢？
因为是无符号数，而无符号数范围是0-42亿左右，那我们不妨传入最大值，即-1
bitset<-1> bs1;
你可能会有疑问，多了两亿不会多很多内存吗？
答案是不会，占满其实也就512M，具体我们看下面的实现
我们先看成员变量的建立，由于在编程语言中，我们没有按位存储的存储类型（至少C/C++是没有的）
所以这里我们采用最小存储类型char，char占1个字节，可是我们需要的是1bit，那么我们该如何做呢？
接下来我们看位图的构造函数，我们用模板参数/8，初始化每个字节为全0，多+1是由于数组的索引从0开始，所以需要额外的一个元素来确保能够容纳最高索引 N-1 的位，这样我们的空间开辟完毕，也初始化完毕
接下来我们看set函数（此函数用于入位图）
void set(size_t x) { size_t i = x / 8; size_t j = x % 8; _bits[i] |= (1 << j); }
用于将指定索引 x 处的位设置为1：
size_t i = x / 8;：这一行代码计算索引x对应的字节（byte）索引。因为_bits是一个vector<char>，每个元素代表一个字节（8位），所以我们用索引x除以8来得到字节索引。size_t j = x % 8;：这一行代码计算索引x对应的位在字节中的位置。它使用取模运算来获得余数，表示在字节中的位偏移。_bits[i] |= (1 << j);：这一行代码使用位操作将位图中索引x处的位设置为1。具体来说：
(1 << j)会创建一个只有第j位为1的整数。例如，如果j是3，那么(1 << 3)将得到二进制00001000。_bits[i] |= (1 << j)利用位或运算符将_bits[i]中对应的位和上面的整数进行“或”操作，将指定位设置为1。
这个函数的目的是在位图中设置指定索引 x 处的位为1，从而表示该位置存在某种标记或状态。
reset函数（此函数用于出位图）
void reset(size_t x) { size_t i = x / 8; size_t j = x % 8; _bits[i] &= ~(1 << j); }
用于将指定索引 x 处的位重置为0：
size_t i = x / 8;：这一行代码计算索引x对应的字节（byte）索引，以确定所在的字节。size_t j = x % 8;：这一行代码计算索引x对应的位在字节中的位置，以确定位的偏移。_bits[i] &= ~(1 << j);：这一行代码使用位操作将位图中索引x处的位重置为0。具体来说：
(1 << j)会创建一个只有第j位为1的整数。例如，如果j是3，那么(1 << 3)将得到二进制00001000。~(1 << j)会创建一个只有第j位为0、其余位为1的整数，以便将第j位重置为0。_bits[i] &= ~(1 << j)利用位与运算符将_bits[i]中对应的位和上面的整数进行“与”操作，将指定位设置为0。
这个函数的目的是在位图中重置指定索引 x 处的位为0，从而表示该位置不存在某种标记或状态。
test函数（此函数用于查询数是否在位图中）
bool test(size_t x) { size_t i = x / 8; size_t j = x % 8; return _bits[i] & (1 << j); }
用于检查指定索引 x 处的位是否为1：
size_t i = x / 8;：这一行代码计算索引x对应的字节（byte）索引，以确定所在的字节。size_t j = x % 8;：这一行代码计算索引x对应的位在字节中的位置，以确定位的偏移。_bits[i] & (1 << j)：这一行代码使用位操作检查位图中索引x处的位是否为1。具体来说：
(1 << j)会创建一个只有第j位为1的整数。例如，如果j是3，那么(1 << 3)将得到二进制00001000。_bits[i] & (1 << j)利用位与运算符将_bits[i]中对应的位和上面的整数进行“与”操作，以检查该位是否为1。如果结果为0，表示该位为0；如果结果为非0，表示该位为1。
这个函数的目的是检查位图中指定索引 x 处的位是否为1，以判断某种标记或状态是否存在。如果该位为1，函数返回true，表示存在；如果该位为0，函数返回false，表示不存在。
实际上在C++中是加入了位图这个容器的，名称和我这一样，这里我们模拟实现是为了更好的理解这个概念
库中的bitset功能更多，但主要函数也是这几个
3. 位图相似应用
给定100亿个整数，如何找到只出现一次的整数？
其实这种问题和我们上面的示例的题目类似，解决方式只需略作改动。
我们可以使用两个位图分别标记存在次数，也就类似key value型，这里我们只需要标记3种情况
代码如下：
template<size_t N> class twobitset { public: void set(size_t x) { bool inset1 = _bs1.test(x); bool inset2 = _bs2.test(x); // 00 if (inset1 == false && inset2 == false) { // -> 01 _bs2.set(x); } else if (inset1 == false && inset2 == true) { // ->10 _bs1.set(x); _bs2.reset(x); } else if (inset1 == true && inset2 == false) { // ->11 _bs1.set(x); _bs2.set(x); } } void print_once_num() { for (size_t i = 0; i < N; ++i) { if (_bs1.test(i) == false && _bs2.test(i) == true) { cout << i << endl; } } } private: bitset<N> _bs1; bitset<N> _bs2; };
这里我们需要实现一个双位图（Two-Bitset）数据结构。双位图是一种在每个索引上存储两个位的数据结构，通常用于表示每个索引的两种状态。代码解析如下：
set(size_t x)函数：
- 首先，它检查
_bs1和_bs2位图中索引x处的状态。 - 如果
_bs1中索引x处的位为0，而_bs2中索引x处的位也为0（00状态），则将_bs2中索引x处的位设置为1，将其状态变为01。 - 如果
_bs1中索引x处的位为0，而_bs2中索引x处的位为1（01状态），则将_bs1中索引x处的位设置为1，将_bs2中索引x处的位重置为0，将其状态变为10。 - 如果
_bs1中索引x处的位为1，而_bs2中索引x处的位为0（10状态），则将_bs1和_bs2中索引x处的位都设置为1，将其状态变为11。
print_once_num()函数：
- 这个函数用于打印那些状态为10（01状态的相反）的索引。这表示只在
_bs2中为1而在_bs1中为0的索引。这些索引被认为在双位图中只出现一次。
1个文件100亿int，1G内存，如何找到不超过2次的所有整数
两个题目其实相似，无非就是多一种状态，原理同上
