何时使用位图？

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

1. 遍历，时间复杂度O(N)
2. 排序(O(NlogN))，利用二分查找: logN
   上述两种方法都不是很好，因此有了位图的用武之地

位图（表示一个数在不在）

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

用位图解决上述问题需要的空间为：

因此位图需要开42亿9千万个比特即500M的空间：

位图的简单实现（C++库中有：bitset）

#include<iostream>
#include<vector>
using namespace std;


namespace cola
{
	template<size_t N>
	class bitset
	{
	public:
		bitset()
		{
			//假设为7：7/8 = 0或10：10/8 = 1，因此最后加一个1防止空间不够用
			_bits.resize(N / 8 + 1, 0);//初始化为全0
		}

		//将数据存入位图
		void set(size_t x)
		{
			//计算x会放到第几个字节
			size_t i = x / 8;

			//计算x会放到第几位
			size_t j = x % 8;

			//存入位图中（位图置为1）
			_bits[i] |= (1 << j);
		}

		//将数据从位图中移除
		void reset(size_t x)
		{
			//计算在第几个字节
			size_t i = x / 8;

			//计算第几位
			size_t j = x % 8;

			//将数据移除（位图置为0）
			_bits[i] &= ~(1 << j);
		}

		//查看数据是否存在（位图是否为1）
		bool test(size_t x)
		{
			//计算在第几个字节
			size_t i = x / 8;

			//计算第几位
			size_t j = x % 8;

			return _bits[i] & (1 << j);
		}
	private:
		vector<char>_bits;
	};

	void test_bitset()
	{
		bitset<100> bs;
		bs.set(5);
		bs.set(4);
		bs.set(10);
		bs.set(20);

		cout << bs.test(5) << endl;
		cout << bs.test(4) << endl;
		cout << bs.test(10) << endl;
		cout << bs.test(20) << endl;
		cout << bs.test(21) << endl;
		cout << bs.test(6) << endl << endl;

		bs.reset(20);
		bs.reset(10);
		bs.reset(5);

		cout << bs.test(5) << endl;
		cout << bs.test(4) << endl;
		cout << bs.test(10) << endl;
		cout << bs.test(20) << endl;
		cout << bs.test(21) << endl;
		cout << bs.test(6) << endl; 
	}
}

int main()
{

	cola::test_bitset();

	system("pause");
	return 0;
}

测试结果：

位图相关题目

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

代码实现

//设计两个位图配合的类
	template<size_t N>
	class TwoBitSet
	{
	public:
		//插入数据
		void Set(size_t x)
		{
			//查看数据出现了几次
			//00 没出现过
			if (!_bit1.test(x) && !_bit2.test(x))// 00 -> 01
			{
				//设为 01 表示出现了1次
				_bit2.set(x);
			}
			//01 出现1次
			else if (!_bit1.test(x) && _bit2.test(x)) // 01 -> 10
			{
				//设为 10 表示出现了2次	
				_bit1.set(x);  //位图1置为1
				_bit2.reset(x);//位图2置为0
			}
			// 10 表示已经出现2次或以上，不用处理
		}

		//查找出现一次的数
		void PrintOnceNum()
		{
			for (size_t i = 0; i < N; ++i)
			{
				// 01 出现1次
				if (!_bit1.test(i) && _bit2.test(i))
				{
					cout << i << endl;
				}
			}
		}

	private:
		bitset<N> _bit1;
		bitset<N> _bit2;
	};

	void TestTwoBitSet()
	{
		int a[] = { 99,0,4,50,33,44,2,5,99,0,50,99,50,2 };
		TwoBitSet<100> bs;
		for (auto e : a)
		{
			bs.Set(e);
		}

		bs.PrintOnceNum();
	}

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

void TestFindIntersection()
	{
		int a1[] = { 5, 30, 1, 29, 10};
		int a2[] = { 8, 10, 11, 9, 30, 10, 30};

		bitset<30>b1;
		bitset<30>b2;

		for (auto e : a1)
		{
			b1.set(e);
		}

		for (auto e : a2)
		{
			b2.set(e);
		}

		//因为按字节查找，因此要30 / 8 + 1
		for (int i = 0; i < (30 / 8 + 1); i++)
		{
			size_t res = b1._bits[i] & b2._bits[i];
			cout << res << endl;
		}
	}

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