bitset详解

本文旨在讲解位图的原理，以及位图有什么作用，如何实现位图。希望读完本篇文章能对小伙伴们有一定的收获！上干货！

什么是位图

位图就是bitmap的缩写，所谓bitmap，就是用每一位来存放某种状态，适用于大规模数据，该数据都是不重复的简单数据。通常是用来判断某个数据存不存在的。

C++中以bitset定义为位图，下面我们来看一下C++对位图的解释吧！

在C++中，位图以非类型的模版参数定义，简单翻译下来就是：位图存储比特位（其存储的元素只有0/1两个值）。

位图的应用：（海量数据的处理）

位图通常用于海量数据的处理！

例如如果有40亿个无符号整数，那么如何快速判断一个数是否存在与这40亿个无符号整数数中呢？

可能有的小伙伴首先想到的就是遍历一遍数组，然后判断即可！那么如果是否真的能遍历呢？对于40亿个无符号整数，其占用大约15G的空间！

40亿*4=160亿字节/1024/1024/1024=14.9 

对于40亿个数字，大约占了15G内存，大多计算机根本放不下这么大的数据！那么该如何解决呢？此时就引进了位图，位图其只用一个比特位代表一个数字！所以40亿个比特位就转化为内存大约为：40亿/8/1024/1024/1024 =0.46G,占用不到0.5G的内存，显然使用位图的方式可以解决！那么该如何使用位图呢？

我们只需要求出这个数字对应于位图的哪一位即可，如果该数字存在，那么就将改为置为1即可，否则就置为0。

对于位图，我们定义一个vector<char>的向量，每个元素为char类型的，占8个字节！我们只需要求出数字在这个vector中对应的位置即可，存在的话，将对应为设为1，下面来看一个例子！

对于数字1,5,7,15,22，在位图中就是这样存储的！

这是怎么计算的呢？下面来讲解一下：对于vector,内部放的是char类型的，因为char占8个字节，所以我们只需要将数字除一个8，就能得到在第几个字节中，然后进行取余，就可以得到在当前字节的第几个比特位！

例如15

15/8=1   15%8=7；所以15就在下标为1的那个字节中，在当前字节中的第7个比特位！其他也是同理的！

既然了解了位图的存储方式，那么我们就来简单实现一下位图这个结构吧！

实现位图

参考C++中的位图的一些功能，我们就简单实现一些位图的操作！

我们就来简单实现test(),set(),reset(),这几个函数吧！

set()函数的实现

通过观察C++文档， 我们可以得知，set的作用是将对应的比特位设置为true即为1！

下面我们就来自己实现这个set函数，因为位图的结构是我们自己定义的，那么当我们将位图的底层用vector<int>向量来进行实现的话，我们只需要将除的值和模的值都变成int的比特位即可！

下面我们就以vector<int>向量来进行实现！

		//实现set函数！
		//观察库中的set函数，我们可以发现set函数是将x对应的比特位置为1！
		void set(size_t x)
		{
			//i代表数组中的第几个下标！
			int i = x / 32;

				//j代表的是该下标的第几个比特位！
			int j = x % 32;

			//然后将数组中i位置的第j个比特位置为1即可！
			//将第几个比特位置为1，我们可以使用按位或上1即可！
			_bitset[i] |= 1 << j;
		}

将某一位设置为1，前面我的文章已经讲过了，我也不过多进行解释了，只需要将1左移j位，然后按位与上1即可！

reset()函数的实现！

我们实现库中的第二个reset函数，将pos位置为0。代码如下

//reset的作用是将x对应的位重置为0！
		void reset(size_t x)
		{
			//i代表数组中的第几个下标！
			int i = x / 32;

			//j代表的是该下标中的第几个比特位！
			int j = x % 32;

			//将第i为置为0的操作，只需要进行按位于上个(1左移x=位取反！)即可！
			_bitset[i] &= ~(1 << j);
		}
		

我们将某一位置为0只需要进行将1进行左移j位，然后取反按位与即可!!

test()函数的实现！

test()函数用于检验当前位是否被设置，如果被设置就返回true，否则返回false，即判断当前位是否为1，为1返回true，为0返回false!

bool test(size_t x)
		{
			//i代表数组中的第几个下标！
			int i = x / 32;

			//j代表的是该下标中的第几个比特位！
			int j = x % 32;

			//按位与上个1左移j位
			return _bitset[i]&(1 << j);

		}

至此位图相关函数已经实现，下面我们看一下位图的成员的实现，以及构造函数！

成员就是我们刚才讲的，其中vector中的类型可以换成char，long long 等类型！

对于构造函数！

因为是vector容器，其resize的参数默认是n个存储元素的大小，所以我们多开辟一个该类型的空间，防止因不能整除导致空间不够的问题！

 位图实现的所有代码

#pragma once


//自己模拟实现位图的操作！

//加上命名空间与库中的bitset进行区分
#include<vector>
namespace Zhj
{
	//非类型的模版！
	template<size_t	N>
	class Bitset
	{
	public:
		//构造函数！
		Bitset()
		{
			//对位图进行初始化！
			//为容器分配空间，因为是整形类型的容器，所以需要开辟N/32   但是可能除不尽，所以多开辟一个int的空间！
			_bitset.resize(N / 32 + 1);
		}

		//实现set函数！
		//观察库中的set函数，我们可以发现set函数是将第x为置为1！
		void set(size_t x)
		{
			//i代表数组中的第几个下标！
			int i = x / 32;

				//j代表的是该字节中的第几个比特位！
			int j = x % 32;

			//然后将数组中i位置的第j个比特位置为1即可！
			//将第几个比特位置为1，我们可以使用按位或上1即可！
			_bitset[i] |= 1 << j;
		}

		//reset的作用是将第x为重置为0！
		void reset(size_t x)
		{
			//i代表数组中的第几个下标！
			int i = x / 32;

			//j代表的是该字节中的第几个比特位！
			int j = x % 32;

			//将第i为置为0的操作，只需要进行按位于上个(1左移x=位取反！)即可！
			_bitset[i] &= ~(1 << j);
		}
		

		//检测第x位是什么！
		bool test(size_t x)
		{
			//i代表数组中的第几个下标！
			int i = x / 32;

			//j代表的是该字节中的第几个比特位！
			int j = x % 32;

			//按位与上个1左移j位
			return _bitset[i]&(1 << j);

		}
	private:
		//默认以存储int类型来构造！

		vector<int> _bitset;

	};
}

海量数据的处理

既然了解了位图，以及其实现，那么我们就来看一些关于位图的题目吧！

1.给定100亿个整数，设计算法找到只出现一次的整数？

对于这道题，首先想到的肯定是使用位图，因为如果不使用位图，内存空间是肯定不够的！那么我们该如何使用位图来解决问题呢?

对于整数类型，其取值范围为0~2^32-1;对于100亿个数字，肯定是存在重复的，那么我们就需要创建两个位图，用于统计出现的次数！

位图1 s1， 位图2 s2。

我们可以这样进行统计次数！

0   0                 代表0次！

0   1                代表一次！

1   0                 代表两次即以上！ 

我们只需要创建两个位图将该数字对应的位数进行统计即可！我们可以使用库中的bitset，来实现，我们自己来实现一个由两个位图构成的位图！

#include<bitset>
#include<iostream>
#include<vector>
using namespace std;



template<size_t	N>
class twobitset
{	
public:
	void set(size_t x)
	{ 
		//00  --> 01   
		if (_b1.test(x) == false && _b2.test(x) == false)
		{
			_b2.set(x);			//一次！
		}
		//01->10
		else if (_b1.test(x) == false && _b2.test(x) == true)
		{
			_b1.set(x);  //两次及以上！
			_b2.reset(x);
		}
	}

	void printonce()
	{
		for (size_t i = 0; i < N; i++)
		{
			if (_b1.test(i) == false && _b2.test(i) == true)
			{
				cout << i<<endl;
			}
		}
	}

private:
		bitset<N> _b1;
		bitset<N> _b2;
};

下面来看测试函数！

 #define  _CRT_SECURE_NO_WARNINGS 1
#include"TwoBitset.h"
#include<bitset>

int main()
{
	twobitset<100> bs;

	int a[] = { 1,51,34,5,16,7,9,8,8,9,51 };
	for (auto ch : a)
	{
		bs.set(ch);
	}
	
	bs.printonce();
	return 0;
}

运行结果如下：

确实把我们只出现一次的数字进行的打印出来，那么将100亿个整数放入，那也是可以的！

 2. 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？

因为还是海量数据，所以还是使用的位图思想，我们需要创建两个位图，然后将这100亿个数字利用set函数放到位图中，然后将这两个位图的各个位置进行按位与，把按位与的结果最后利用test函数检测为1的状态，为1的就是交集！

3. 位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数。

与第一题一样，只不过需要多加一个条件即可！即出现两次的也要打印，所以我们也要记录10的存在，当两次以上的结果我们记录为11即可即可！代码如下：

#include<bitset>
#include<iostream>
#include<vector>
using namespace std;



template<size_t	N>
class twobitset
{	
public:
	void set(size_t x)
	{ 
		//00  --> 01   
		if (_b1.test(x) == false && _b2.test(x) == false)
		{
			_b2.set(x);			//一次！
		}
		//01->10
		else if (_b1.test(x) == false && _b2.test(x) == true)
		{
			_b1.set(x);  //两次！
			_b2.reset(x);
		}
		else if (_b1.test(x) == true && _b2.test(x) == false)
		{
			_b2.set(x);    //两次以上的情况！
            
		}
	}

	void prinlesstwo()//打印两次及以下！
	{
		for (size_t i = 0; i < N; i++)
		{
			if (_b1.test(i) == false && _b2.test(i) == true)
			{
				cout << i<<endl;
			}
			else if (_b1.test(i) == true && _b2.test(i) == false)
			{
				cout << i << endl;
			}
		}
	}

private:
		bitset<N> _b1;
		bitset<N> _b2;
};

 至此，位图的相关介绍已经完毕，希望读完本篇文章，能对读者有一定的收获！