【C++】哈希-bitset位图与模拟

目录

1.位图

1.1什么是位图 

1.2位图的作用 

 2.bitset应用

 2.1bitset构造

2.2bitset成员函数与使用 

3.bitset模拟实现 

构造函数 

set

 reset

 test

flip

count 

size 

 none,any

---

1.位图

在前文中我们介绍了哈希的一些内容，接下来我们介绍一个新奇的玩意，位图。 

1.1什么是位图 

• 位图其实就是哈希的变形，同样通过映射来处理数据。
• 位图本身并不存储数据，而是存储标记通过一个比特位来标记这个数据是否存在，1代表存在，0代表不存在。
• 位图通常情况下用在数据量庞大，且数据不重复的情景下判断某个数据是否存在。

相比通过上面的介绍，各位还是不知道位图有啥作用。接下来我们说一下位图的作用。

1.2位图的作用 

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

1整数=4字节=32bit。
 
40亿个整数 = 160亿个字节
而1GB = 1024MB
1024MB = 1024 * 1024KB
1024 * 1024KB = 1024 * 1024 * 1024B(yte )≈ 10亿字节
综上1GB ≈ 10亿字节
   16GB ≈ 160亿字节

遍历时间复杂度O(N)；排序(O(NlogN))利用二分查找: logN；这两种方式除了效率不够高，还有个问题是内存无法完全同时加载40亿个整数需要的16G大小空间。

我们也可以用set容器，但是底层的红黑树存放这么多数据也吃不消所以我们用位图来解决这个问题。

1个整形是32bit位，就比如整数在计算机中以二进制来存储的。而这32个位置上只有0或1，那我们可以让1表示有数据，0表示没存放数据。我们以32比特位表示一个单元。

如果采用这种方法，只需占500M内存就可以：

1G = 2^30Byte ≈ 10亿字节
(2^32 - 1)Byte ≈ 40亿字节 ≈ 4G
1Byte = 8bit
(2^32 - 1)bit = 4G/8 ≈ 500MB

例如：int a[]={2,5,7,19,24,30}
 

 2.bitset应用

 2.1bitset构造

 位图构造有三种形式，这里我们直接上代码。

void testbitset1()
{
    //1.创建一个16位位图，初始0
	std::bitset<16> foo;  // 创建一个16位位图
    //2.赋值16进制
	std::bitset<16> bar(0xfa2);   //16进制 4002
   //3.用0，1赋值或者string
	std::bitset<16> baz(std::string("0101111001"));
	std::bitset<16> bs1("011010001");
	//foo : 0000000000000000
	//bar : 0000111110100010   4002
	//baz : 0000000101111001
	//bs1 : 0000000011010001
	std::cout << "foo: " << foo << '\n';
	std::cout << "bar: " << bar << '\n';
	std::cout << "baz: " << baz << '\n';
	std::cout << "bs1: " << bs1 << '\n';
}

2.2bitset成员函数与使用 

成员函数	功能
set	设置指定位或所有位
reset	清空指定位或所有位
test	获取指定位的状态
flip	反转指定位或所有位
count	获取被设置位的个数
size	获取可以容纳的位的个数
any	如果有任何一个位被设置则返回true
none	如果没有位被设置则返回true
all	如果所有位都被设置则返回true

 

void testbitset2()
{
	std::bitset<16> bs1;
	bs1.set(2);  //0000000000000100
	cout << bs1 << endl;
	bs1.set(4);
	bs1.set(5);  //0000000000110100
	cout << bs1 << endl;
	//获取指定位置的状态
	cout << bs1.test(5) << endl;  //位置5的状态是1
	cout << bs1.test(10) << endl; //位置10的状态是0
	//反转
	cout << bs1.flip(4) << endl;   //反转第4位
	cout << bs1.flip() << endl;    //反转所有位
	//清空
	cout << bs1.reset(10) << endl;   //清空第10位
	cout << bs1.reset()<//全清
	//设置
	cout <set(1)<// 设置第一位
	cout << bs1.all() << endl;
}

bitset运算符那个就不讲了。我们直接模拟实现一下。

3.bitset模拟实现 

• 模拟bitset就是用一个普通的数组来存储数据以达到模拟的目的。
• 一个单元我们分成4个小组，每个小组8个位置。存放一个数据要先判断在那个单元，然后是那个小组，那个位置。
• 找到对应单元后，数据/8=对应小组；数据%8=对应位置。

• 如果我们以一个整型作为比特位的容器，那么如果要求0~N范围的比特位，就需要有N/32+1 个整型来容纳这些比特位，同理如果以char为容器，则需要N/8+1个char来容纳N个比特位。这里我们用vector数组作为底层容纳比特位的容器。之所以+1是怕开的空间存不下，所以多开一个，就算剩下也剩不了多少。

namespace cpp
{
	//N个比特位的位图
	template<size_t N>
	class bitset
	{
	public:
		//构造函数
		bitset();
		//把value映射的位标记成1
		void set(size_t value);
		//把value映射的位标记成0
		void reset(size_t value);
		//判断指定位value的状态是否为1
		bool test(size_t value);
		//翻转指定位置
		void flip(size_t value);
		//获取位图中可以容纳位N的个数
		size_t size()
		//统计set中1的位数
		size_t count();
		//判断所有比特位若无置为1，返回true
		bool none();
		//判断位图中是否有位被置为1，若有则返回true
		bool any();
		//全部NUM个bit位被set返回true
		bool all();
	private:
		vector<char> _bits;//位图
	};
}

这里我们用的存储类型是char。

构造函数 

 构造还是构造，但是文章已不是当年的文章了。

public :
		//构造函数
		bit_set
		{
			_bits.resize(N / 8 + 1,0);   // 全部赋值0
		}

之所以+1是因为如果数据的个数不是8的倍数时，可以再存进去，要不那多余的数据咋弄？

set

 把映射的位置标记为1（把设置位置标记为1）。

例如：value=13;

//映射的位置标为1
		void set(size_t value)
		{
			size_t i = value / 8;  //找到小组
			size_t j = value % 8;   //找到位置
			//把对应位置标记为1
			_bits[i] |= 1 << j;     //或运算，有1则1
		}

 reset

清空指定位或所有位 

这个和set正好相反，这个是把指定位置的数变成0，最后一步变化，其他不变，先按位取反，在按位与即可。j<<1按位取反后变成1，在按位与_bits[i]后就设置成0了。

//把value映射的位标记成0
		void reset(size_t value)
		{
			size_t i = value / 8;  //找到小组
			size_t j = value % 8;   //找到位置
			//把对应位置标记为1
			_bits[i] &=~(( 1 << j));     //先按位取反在与运算
		}

 test

 判断指定位置是否为1

这个跟上面的reset就缺少一个按位取反。只进行一个按位与运算即可

//判断指定位value的状态是否为1
		bool test(size_t value)
		{
			size_t i = value / 8;  //找到小组
			size_t j = value % 8;   //找到位置
			//把对应位置标记为1
			_bits[i] &= (1 << j);  
		}

flip

指定位置数据翻转： 如果是1变成0，0变成1。

这个按位异或就行了 ,相同为0，1变成0，相异为1，0^1=1

//翻转指定pos
		void flip(size_t value)
		{
			size_t i = value / 8;  //找到小组
			size_t j = value % 8;   //找到位置
			//把对应位置标记为1
			_bits[i] ^= (1 << j);
		}

count 

统计位图中出现的1的次数 

这个跟前面几个就不一样了。

这个是n&n-1

 

size_t count()
		{
			size_t count = 0;
			for (auto e : _bits)
			{
				int n = e;   //再设置个中间变量，别直接用e
				while (n)
				{
					n = n & (n - 1);
					count++;
				}
			}
			return count;
		}

size 

size的作用是获取位图中可以容纳位N的个数

size_t size()
		{
			return N;
		}

 none,any

none是查找位图中是否全部是0，是就返回true,不是返回false。

any是查找位图中是否有1，是就返回true,没有返回false。any可以复用none。完整

        bool none()
		{
			//遍历每个char
			for (auto e : _bits)
			{
				if (e != 0)//位图中有位置被置为1，返回false
					return false;
			}
			return true;//说明全为0，返回true
		}
		//若有位置为1，返回true
		bool any()
		{
			 return !none;
		}

 完整代码可到gitee查看

C++ 进阶: 本仓库存放一些较难C++代码https://gitee.com/j-jun-jie/c---advanced.git