位图的引入

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

1. 遍历，时间复杂度O(N)
2. 排序(O(NlogN))，利用二分查找: logN
3. 位图解决
   数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。比如：
   
   无符号整数总共有232个，因此记录这些数字就需要232个比特位，也就是512M的内存空间，内存消耗大大减少。

位图的概念

所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。

位图的使用

位图的定义

1.构造一个16位的位图，所有位都初始化为0。

bitset<16> bs1; //0000000000000000

2. 构造一个16位的位图，根据所给值初始化位图的前n位。

bitset<16> bs2(0xaa6); 

3.构造一个16位的位图，根据字符串中的0/1序列初始化位图的前n位。

bitset<16> bs3(string("10111001")); //0000000010111001

成员函数的介绍

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

int main()
{
    
	bitset<8> bs;
	bs.set(2); //设置第2位
	bs.set(4); //设置第4位
	cout << bs << endl; //00010100
	
	bs.flip(); //反转所有位
	cout << bs << endl; //11101011
	cout << bs.count() << endl; //6

	cout << bs.test(1) << endl; 

	return 0;
}

注意： 使用成员函数set、reset、flip时，若指定了某一位则操作该位，若未指定位则操作所有位。

bitset运算符的使用。

一、对输入输出运算符的使用
bitset容器对>>、<<运算符进行了重载，可以直接对bitset定义出来的对象进行输入输出操作。

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

int main()
{
    
	bitset<8> bs;
	cin >> bs; //00110
	cout << bs << endl; //00000110
	return 0;
}

二、bitset中赋值运算符、关系运算符、复合赋值运算符、单目运算符的使用。

#include <iostream>
#include <string>
#include <bitset>
using namespace std;

int main()
{
    
	bitset<8> bs1(string("10101010"));
	bitset<8> bs2(string("10101010"));
	bs1 >>= 1;
	cout << bs1 << endl; //01010101
//这里我们用的是按位或等运算符，有1位就变成1
	bs2 |= bs1;
	cout << bs2 << endl; //11111111
	return 0;
}

三、bitset中位运算符的使用。

#include <iostream>
#include <string>
#include <bitset>
using namespace std;

int main()
{
    
	bitset<8> bs1(string("10101010"));
	bitset<8> bs2(string("01010101"));
	
	cout << (bs1&bs2) << endl; //00000000
	cout << (bs1|bs2) << endl; //11111111
	cout << (bs1^bs2) << endl; //11111111
	return 0;
}

^{是异或的意思。他的规则是参加运算的两个二进位同号，则结果为0（假），异号则为1（真）即0}0=0,0^1=1,10=0，1^1=0（相同为0，相异为一）；&是与运算，如果两个都是1，则结果是1，否则为0；|是或运算符，两个二进制数中只要有一个是1就为1，也就是除非两个数都是0，才为0。