目录

一、位图相关面试题：

二、位图的优缺点：

三、位图相关的考察题目

四、代码实现

一、位图相关面试题：

给40亿个不重复的无符号整数，没排过序，如何判断一个数是否在这40亿数中
 思路一：暴力查找
 思路二：排序+二分查找
 但是第二种方法对内存的要求太高，1G约等于10亿Byte，1G可存10/4个int，40 / （10 / 4）
 因此大约需要16G，但是因为空间太大，只能将这些数放在硬盘中，而二分查找只能处理内存
 中的有序数组
 思路三：每个数映射一个比特位，即位图

二、位图的优缺点：

有点：增删查改特别快
缺点：只适用于整形

三、位图相关的考察题目

 1、给定100亿个整数，找出只出现一次的整数
    还是使用位图，开两个42亿9000万个比特位的空间，第一个代表2^1，第二个代表2^0
    ，10代表出现两次及以上，00代表未出现，01代表只出现一次，因此对位图进行封装就
    可以完成任务
 2、两个文件中都有一百亿个整数，找出两者的相同的数
 3、一个文件中有100亿个整数，1G内存，找到所有出现次数不超过两次的整数
    与第一题完全类似
 

四、代码实现

#pragma once
#include <vector>

namespace wjl
{
	template<size_t N>
	class bitset
	{
	public:
		bitset()
		{
			_bs.resize(N / 32 + 1);
		}

		//变为1
		void set(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;
			//左移不一定是向左移动，只是第字节序往高字节序移动，左移的左不是方向
			_bs[i] |= (1 << j);
		}

		//变为0
		void reset(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;
			_bs[i] &= (~(1 << j));
		}

		//是1就是真
		bool test(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;
			return _bs[i] & (1 << j);
		}
	private:
		std::vector<size_t> _bs;
	};

	template<size_t N>
	class twobitsets
	{
	public:
		void set(size_t x)
		{
			bool flag1 = _bs1.test(x);
			bool flag2 = _bs2.test(x);
			if (flag1 && !flag2)
			{
				//10 -> 11
				_bs2.set(x);
			}
			else if (!flag1 && flag2)
			{
				//01 -> 10
				_bs1.set(x);
				_bs2.reset(x);
			}
			else if(!flag1 && !flag2)
			{
				//00 -> 01
				_bs2.set(x);
			}
		}

		int getcount(size_t x)
		{
			bool flag1 = _bs1.test(x);
			bool flag2 = _bs2.test(x);
			if (flag1 && !flag2)
			{
				return 2;
			}
			else if (!flag1 && flag2)
			{
				return 1;
			}
			else if (!flag1 && !flag2)
			{
				return 0;
			}
			return 3;
		}
	private:
		bitset<N> _bs1;
		bitset<N> _bs2;
	};
}