位图的详解
位图概念
位图（BitMap/BitSet） 是一种高效存储和操作二进制位的数据结构，核心思想是通过二进制位（0 或 1）表示某种状态或信息。它广泛用于需要紧凑存储和快速位操作的场景，例如去重、快速查找、布隆过滤器等。
位图的本质是一个数组，用来存放0和1。
位图通过自身数组中的每个位来代表集合(我们要处理的数据)中的元素，每个位是0或1，代表元素的存在与否(0,不存在；1,存在)。
位图的核心思想
用二进制位表示信息：每个位（0 或 1）可以表示一个布尔值（例如是否存在、是否有效）
空间高效：1 个整数（如 int 或 uint32_t）可以存储 32 个独立状态，1 亿个状态仅需约 12MB 内存
位图的核心操作
位图的核心操作操作作用代码示例时间复杂度时间复杂度设置位将位置设置为1_bits[i] |= (1 << j)O(1)清除位将位置设置为0bits[i] &= ~(1 << j)O(1)查询位检查位置是否为1bool exists = bits[i] & (1 << j)O(1)
位图的优势
极致空间效率：
存储 1 亿个状态仅需约 12MB（1 亿 / 8 / 1024² ≈ 11.92MB）。
对比哈希表：存储 1 亿个整数需要约 400MB（假设每个整数占 4 字节）。
操作速度快
所有操作（设置、清除、查询）均为 O(1) 时间复杂度。
位图的实现
上面列出了位图的优点，那么位图该怎么实现呢？
根据上面列出的表格，位图的实现主要包含三个核心的接口：设置（设为1）、重置（设为0）、判断（是0还是1）。
对于每一步可以看注释
namespace bit
{
//模板参数表示位图的总位数
template
class bitset
{
public:
bitset()
{
//加1是确保当N不是32的倍数时，仍有足够的空间
_bits.resize(N / 32 + 1, 0);
}
void set(size_t x) // 设为1
{
//计算在哪个int组里面
size_t i = x / 32;
//一个int里有32位，x % 32 计算出在int组里面的具体哪一位
size_t j = x % 32;
// | 按位或 ：某位与 1 或 ，结果必为1，其他位不受影响
_bits[i] |= (1 << j);
}
void reset(size_t x)// 设置为0
{
size_t i = x / 32;
size_t j = x % 32;
//先按位取反，目标位为0， 其他位为1， 任何数 &1 都是它本身， &0 都是0
_bit[i] &= ~(1 << j);
}
bool test(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;
//任何数 &1 都是它本身
//如果是1 就返回 true 否则返回false
return _bits[i] & (1 << j);
}
private:
//每个int存储32位
vector
};
给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中
1.首先我们考虑遍历这40亿个数，但是这样效率太低了，时间复杂度是O(N)
2. 可以考虑排序，(O(NlogN))，利用二分查找: logN
3，也可以考虑搜索树或者哈希表，但是40亿个整数需要存储多少内存-> 16G 考虑当内存开不了这么大的空间
4.所以我们使用位图解决
数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。比如
那么，认识了位图，位图有什么应用呢？
快速查找某个数据是否在一个集合中 排序 + 去重 求两个集合的交集、并集 操作系统中磁盘块标记
扩展：
双位图的扩展
给定100亿个整数，设计算法找到只出现一次的整数？
思考：在100亿个整数中只找出出现一次的整数，那么这里我们可以考虑使用key-value模型，此时我们可以考虑双位图来解决。
1.定义双位图结构
使用两个位图（_bits1和_bits2）,每一个位图的每一位组合表示一个整数出现的次数状态：
00：未出现过01：出现过一次10：出现两次以上
2。遍历所以整数并更新状态：
代码实现：
template
class twobitset
{
public:
void set(size_t x)
{
// 00 - 01 出现0次
// 01 - 10 出现1次
// 10 - 11 出现2次或以上
// 11 - 不变
if (_bs1.test() == false && _bs2.test() == false)
{
_bs2.set(x);
}
else if (_bs1.test() == false && _bs2.test() == true)
{
_bs1.set(x);
_bs2.reset(x);
}
else if (_bs1.test() == true && _bs2.test() == false)
{
_bs2.set(x);
}
}
void Print()
{
for (size_t i = 0; i < N; i++)
{
if (_bs1.test() == false && _bs2.test() == true)
{
cout << "1 - > " << i << endl;
}
else if (_bs1.test() == true && _bs2.test() == false)
{
cout << "2 - > " << i << endl;
}
}
cout << endl;
}
private:
bitset
bitset
};
}