C++ STL(十) --------- 位图模拟实现

目录

1.位图的概念

2.位图的模拟实现

接口总览

1.位图的概念

(1)位图引出

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

• 1. 遍历，时间复杂度O(N)
• 2. 排序(O(NlogN))，利用二分查找: logN
• 3. 位图解决

②位图解决

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

(2)基本概念

2.位图的模拟实现

• 接口总览

	//模拟实现位图
	template<size_t N>
	class bitset
	{
	public:
		//构造函数
		bitset();
 
		//设置位
		void set(size_t pos);
 
		//清空位
		void reset(size_t pos);
 
		//反转位
		void flip(size_t pos);
 
		//获取位的状态
		bool test(size_t pos);
 
		//获取可以容纳的位的个数
		size_t size();
 
		//获取被设置位的个数
		size_t count();
 
		//判断位图中是否有位被设置
		bool any();
 
		//判断位图中是否全部位都没有被设置
		bool none();
 
		//判断位图中是否全部位都被设置
		bool all();
 
		//打印函数
		void Print();
	private:
		vector<int> _bits; //位图
	};

 (1)构造函数

• 在构造位图时，我们需要根据所给位数N，创建一个N位的位图，并且将该位图中的所有位都初始化为0
• 一个整型有32个比特位，因此N个位的位图就需要用到N/32个整型，但是实际我们所需的整型个数是N/32+1，因为所给非类型模板参数N的值可能并不是32的整数倍 ，此时我们要向上取整

//构造函数
bitset()
{
	_bits.resize(N / 32 + 1, 0);
}

(2)比特位操作设置

①set成员函数用于设置位

1. 计算出该位位于第 i 个整数的第 j 个比特位。
2. 将1左移 j 位后与第 i 个整数进行或运算即可。

	void set(size_t pos) //把x映射的位标记成1
	{
		assert(pos < N);
		//算出x映射的位在第几个整数，
		//算出x映射的位在这个整数的第几位。
 
		int i = pos / 32;
		int j = pos % 32;
 
		_bits[i] |= (1 << j);  //移位运算符的优先级低
	}

②reset成员函数用于清空位

1. 计算出该位位于第 i 个整数的第 j 个比特位。
2. 将1左移 j 位再整体反转后与第 i 个整数进行与运算即可。

//清空位
void reset(size_t pos)
{
	assert(pos < N);
 
	//算出pos映射的位在第i个整数的第j个位
	int i = pos / 32;
	int j = pos % 32;
	_bits[i] &= (~(1 << j)); //将该位设置为0（不影响其他位）
}

③flip成员函数用于反转位。 

1. 计算出该位位于第 i 个整数的第 j 个比特位。
2. 将1左移 j 位后与第 i 个整数进行异或运算即可。

//反转位
void flip(size_t pos)
{
	assert(pos < N);
 
	//算出pos映射的位在第i个整数的第j个位
	int i = pos / 32;
	int j = pos % 32;
	_bits[i] ^= (1 << j); //将该进行反转（不影响其他位）
}

 ④test成员函数用于获取位的状态

1. 计算出该位位于第 i 个整数的第 j 个比特位。
2. 将1左移 j 位后与第 i 个整数进行与运算得出结果。
3. 若结果非0，则该位被设置，否则该位未被设置。

//获取位的状态
bool test(size_t pos)
{
	assert(pos < N);
 
	//算出pos映射的位在第i个整数的第j个位
	int i = pos / 32;
	int j = pos % 32;
 
	if (_bits[i] & (1 << j)) //该比特位被设置
		return true;
	else //该比特位未被设置
		return false;
}

(3)统计相关

①size成员函数用于获取位图中可以容纳的位的个数

• 直接将所给非类型模板参数进行返回即可。

//获取可以容纳的位的个数
size_t size()
{
	return N; 
}

②count成员函数用于获取位图中被设置的位的个数 

1. 将原数 n 与 n - 1 进行与运算得到新的 n 。
2. 判断 n 是否为0，若 n 不为0则继续进行第一步。

• 如此进行下去，直到 n 最终为0，此时该操作进行了几次就说明二进制中有多少个1。
• 因为该操作每进行一次就会消去二进制中最右边的1

//获取被设置位的个数
size_t count()
{
	size_t count = 0;
	//将每个整数中1的个数累加起来
	for (auto e : _bits)
	{
		int num = e;
		//计算整数num中1的个数
		while (num)
		{
			num = num&(num - 1);
			count++;
		}
	}
	return count; //位图中1的个数，即被设置位的个数
}

 (4)打印函数

• 打印函数，便于检查我们上述代码的正确性，打印位图时遍历位图所包含的比特位进行打印即可

//打印函数
void Print()
{
	int count = 0;
	size_t n = _bits.size();
	//先打印前n-1个整数
	for (size_t i = 0; i < n - 1; i++)
	{
		for (size_t j = 0; j < 32; j++)
		{
			if (_bits[i] & (1 << j)) //该位被设置
				cout << "1";
			else //该位未被设置
				cout << "0";
			count++;
		}
	}
 
	//再打印最后一个整数的前N%32位
	for (size_t j = 0; j < N % 32; j++)
	{
		if (_bits[n - 1] & (1 << j)) //该位被设置
			cout << "1";
		else //该位未被设置
			cout << "0";
		count++;
	}
	cout << " " << count << endl; //打印总共打印的位的个数
}