位图（Bitset）的应用及其原理数据结构介绍

一、位图的概念

位图是一个多义词，在数据结构和图像处理领域都有重要应用。作为数据结构时，它主要用于集合的高效表示和运算；作为图像类型时，它则是数字图像的一种基本形式，能够表现丰富的色彩和细节。无论是哪种应用场景下的位图，都体现了其在计算机科学和信息技术领域中的重要地位。

本文主要介绍位图在数据结构上的应用
1.位图是一种基于位操作的数据结构，用于表示一组元素的集合信息。它通常是一个仅包含0和1的数组，其中每个元素（或位）对应集合中的一个元素。
2.当元素存在时，对应位的值为1；不存在时，对应位的值为0。位图通过自身数组中的每个位来代表集合（我们要处理的数据）中的元素，每个位是0或1，代表元素的存在与否。
3.位图常用于判断某个元素是否属于某个集合，或者对多个集合做交集、并集或差集等集合运算
在这里插入图片描述

二、位序列容器Bitset

在C++中，std::bitset 是一个固定大小的位序列容器，它可以被用作位图（Bitmap）来实现一系列布尔值的集合，每个值仅占用一个比特位（bit）。这对于存储和快速查询大量的布尔状态非常有用，比如集合中的元素是否存在、权限检查等。

#include <iostream>  
#include <bitset>  int main() {  // 假设我们需要存储的整数范围是从0到63（总共64个可能的值）  // 因此，我们使用一个64位的bitset  std::bitset<64> bitmap;  // 添加一些整数到集合中（通过设置相应的位）  bitmap.set(10);  bitmap.set(20);  bitmap.set(10); // 重复设置，但bitset会自动忽略  bitmap.set(30);  // 检查整数是否存在于集合中（通过测试相应的位）  std::cout << "Contains 10? " << bitmap.test(10) << std::endl; // 输出: 1 (true)  std::cout << "Contains 50? " << bitmap.test(50) << std::endl; // 输出: 0 (false)  // 移除一个整数（通过清除相应的位）  bitmap.reset(20);  std::cout << "After resetting 20, contains 20? " << bitmap.test(20) << std::endl; // 输出: 0 (false)  // 翻转所有位（可选操作）  bitmap.flip();  std::cout << "After flipping all bits, bitmap: " << bitmap << std::endl;  // 重置整个bitset（回到全0状态）  bitmap.reset();  std::cout << "After resetting the bitset, bitmap: " << bitmap << std::endl;  // 打印bitset的二进制表示（可选）  std::cout << "Initial bitmap (with 10, 30 set): " << bitmap.set(10).set(30) << std::endl;  return 0;  
}

三、位图的原理模拟实现

template<size_t N>
class bitset
{
public:bitset(){_bits.resize(N / 32 + 1, 0);//cout << N << endl;}// 把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);}bool 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;
};

四、位图的应用

下面举几个位图应用的例子：

1.快速查找某个数据是否在一个集合中

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中

在内存中，1G大约可以存储10亿字节左右，40亿整数大概16G，一般的容器肯定是存不下的，所以我们可以用位图的方法去解答，
用bit位来存，每位存一个，大约16/32为512mb左右
在这里插入图片描述

数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在

2. 排序 + 去重

给定100亿个整数，设计算法找到只出现一次的整数？
在这里插入图片描述
创建两个位图，并记录两个位图的状态，例如没有就是（0,0），一次就是（1,0），两次就是（0,1）

template<size_t N>class two_bit_set{public:void set(size_t x){// 00 -> 01if (_bs1.test(x) == false&& _bs2.test(x) == false){_bs2.set(x);}else if (_bs1.test(x) == false&& _bs2.test(x) == true){// 01 -> 10_bs1.set(x);_bs2.reset(x);}}bool test(size_t x){if (_bs1.test(x) == false&& _bs2.test(x) == true){return true;}return false;}private:bitset<N> _bs1;bitset<N> _bs2;};

3. 求两个集合的交集、并集等

给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
用两个位图进行比较

void test_bitset3()
{int a1[] = { 5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6 };int a2[] = { 5,3,5,99,6,99,33,66 };bitset<100> bs1;bitset<100> bs2;for (auto e : a1){bs1.set(e);}for (auto e : a2){bs2.set(e);}for (size_t i = 0; i < 100; i++){if (bs1.test(i) && bs2.test(i)){cout << i << endl;}}
}

4. 操作系统中磁盘块标记

位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数
和第一个题目类似，只不过条件变多了

template<size_t N>
class two_bit_set
{
public:void set(size_t x){// 00 -> 01if (_bs1.test(x) == false&& _bs2.test(x) == false){_bs2.set(x);}else if (_bs1.test(x) == false&& _bs2.test(x) == true){// 01 -> 10_bs1.set(x);_bs2.reset(x);}}int test(size_t x){if (_bs1.test(x) == false&& _bs2.test(x) == false){return 0;}else if (_bs1.test(x) == false&& _bs2.test(x) == true){return 1;}else{return 2; // 2次及以上}}private:bitset<N> _bs1;bitset<N> _bs2;
};