玩转C++：探索位图、布隆过滤器与哈希分割的奥秘

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

在位图中我们表示一个数存在，则对应的比特位是1，那么我们可以使用两个比特位表示一个数出现的次数：

       出现0次 -> 00

       出现1次 -> 01

       出现2次及以上 -> 10

那么在插入中就需要做一改进

在插入时对应的是00，那么就改为01，如果是01，就改为10。

代码实现：

namespace count_num
{
	template<size_t N>
	class Oncebitset
	{
	public:
		//插入
		void set(size_t x)
		{
			size_t i = x / 32;    //第几个整型
			size_t j = x % 32;    //第几个比特位
			if (_bs1[x] == false && _bs2[x] == false)   //00
			{
				_bs2.set(x);   //对应的比特位改为1      //01
			}
			else if (_bs1[x] == false && _bs2[x] == true) //01
			{
				_bs1.set(x);   //对应的比特位改为1
				_bs2.reset(x); //对应的比特位改为0     //10
			}
		}
		void PrintOnce()
		{
			for (size_t i = 0; i < N; i++)
			{
				if (_bs1.test(i) == false && _bs2.test(i) == true)
				{
					cout << i << endl;
				}
			}
			cout << endl;
		}
	private:
		bitset<N> _bs1;
		bitset<N> _bs2;
	};
}

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

将这两个文件分别映射到位图中，若一个值在这两个位图中都存在，那么便是交集。

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

同样的还是使用两个比特位来表示一个数出现的次数：

       出现0次 -> 00

       出现1次 -> 01

       出现2次 -> 10

       出现3次及以上 -> 11