C++位图

给定40亿个不重复、没排序的无符号整数，再给一个无符号整数，如何快速判断一个数是否在这40亿个数中？？？

		void Set(size_t x)//把x值对应的标记为置为1
		{
			//计算x位于哪一个char上
		//	size_t i = x / 8;
			size_t i=x >> 3;//相当于x/8
			//计算x位于哪个bit上
			size_t j = x % 8;
			_bit[i] |= (1 << j);
		}

void ReSet(size_t x)//把x值对应的标记置为0
		{
			//计算x位于哪一个char上
			//size_t i = x / 8;
			size_t i = x >> 3;//相当于x/8
			//计算x位于哪个bit上
			size_t j = x % 8;
			_bit[i] &= (~(1 << j));
		}

		bool Test(size_t x)//判断x是否在这堆数里面
		{
			//计算x位于哪一个char上
			//size_t i = x / 8;
			size_t i = x >> 3;//相当于x/8
			//计算x位于哪个bit上
			size_t j = x % 8;
			return _bit[i] & (1 << j);
		}

	template<size_t N>//用非类型模板参数---N为要往位图里存储多少个数
	class  BitSet
	{public:
		BitSet()
		{
            //_bit.resize(N >> 3) + 1);
			_bit.resize(N / 8 + 1);//多开一个
		}

		void Set(size_t x)//把x值对应的标记为置为1
		{
			//计算x位于哪一个char上
		//	size_t i = x / 8;
			size_t i=x >> 3;//相当于x/8
			//计算x位于哪个bit上
			size_t j = x % 8;
			_bit[i] |= (1 << j);
		}

		void ReSet(size_t x)//把x值对应的标记置为0
		{
			//计算x位于哪一个char上
			//size_t i = x / 8;
			size_t i = x >> 3;//相当于x/8
			//计算x位于哪个bit上
			size_t j = x % 8;
			_bit[i] &= (~(1 << j));
		}

		bool Test(size_t x)//判断x是否在这堆数里面
		{
			//计算x位于哪一个char上
			//size_t i = x / 8;
			size_t i = x >> 3;//相当于x/8
			//计算x位于哪个bit上
			size_t j = x % 8;
			return _bit[i] & (1 << j);
		}

		vector<char> _bit;
	};

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

//测试
void testBitset()
	{
		BitSet<100> bs1;
		BitSet<100> bs2;
		int path1[] = { 1,2,3,4,5 };
		int path2[] = { 1,3,5 };

		for (auto e : path1)
		{
			bs1.Set(e);
		}

		for (auto e : path2)
		{
			bs2.Set(e);
		}

		for (size_t i = 0; i < 100; i++)
		{
			if (bs1.Test(i) && bs2.Test(i))//11
			{
				cout << i << endl;
			}
		}
		}

一个文件有100亿个int，1G内存，设计算法找出次数不超过2次的所有整数

template<size_t N>
	class twoBitset
	{
	public:
		void Set(size_t x)
		{

			if (!bs1.Test(x) && !bs2.Test(x))//两个位图都是0---数据出现0次
			{//00->01
				bs2.Set(x);
			}
			else if (!bs1.Test(x) && bs2.Test(x))//第一个位图是1，第二个位图是0---数据出现1次
			{//01->10
				bs1.Set(x);
				bs2.ReSet(x);
			}
			else //两个位图都是1---数据出现2次
			{//10->11
				
				bs2.Set(x);
			}
			//else//出现3次及以上
			//{
			//	break;
			//}
		}

		void  Printones()
		{
			for (size_t i = 0; i < N; i++)
			{
				if (!bs1.Test(i) && bs2.Test(i))//01
				{
					cout << i << endl;
				}
				else if (bs1.Test(i) && !bs2.Test(i))//10
				{
					cout  << i << endl;
				}
				


			}

		}
	private:
		BitSet<N> bs1;
		BitSet<N> bs2;

	};

给一个超过100G的log file，log中存着IP地址，设计算法找到出现次数最多的IP地址