位图（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映射的位标记成1
	void set(size_t x)
	{
		assert(x <= N);

		size_t i = x / 32;
		size_t j = x % 32;

		_bits[i] |= (1 << j);
	}

	// 把x映射的位标记成0
	void 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 -> 01
			if (_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 -> 01
		if (_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;
};