一、位图概念
1.使用场景
假如给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中？
计算一下40亿个无符号整数会占多大内存呢？
可以采用如下方法：
（1）放进set或unordered_set中，再用find进行查找
（2）排序，再使用二分法查找，排序的时间复杂度是O(N*logN)，二分查找的时间复杂度是O(logN)
但是，16GB的大小，这会很消耗内存，我们不可能把16GB的数据全部加载到内存中。还有另外一种比较节省内存的方式——位图。
2.位图
位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。
数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。比如：
一个bit位代表一个整数在不在，因此现在一个整数大小（4个字节32位）可以表示32个整数在不在，那么对于第一小节的40亿个整数16GB就可以用500MB进行表示了，500MB是可以加载到内存中的，这也提高了效率。
二、位图介绍
1.构造
有3种构造方式：分为默认0、整数、字符串3种类型
1. bitset();//默认 2. bitset (unsigned long val);//参数传整数，10进制或16进制都可以 3. template<class charT, class traits, class Alloc> explicit bitset (const basic_string<charT,traits,Alloc>& str, typename basic_string<charT,traits,Alloc>::size_type pos = 0, typename basic_string<charT,traits,Alloc>::size_type n = basic_string<charT,traits,Alloc>::npos);//字符串
用3种构造方式构造3个位图对象：
1. #include<iostream> 2. #include<string> 3. #include<bitset> 4. using namespace std; 5. 6. int main() 7. { 8. bitset<16> bs1; 9. bitset<16> bs2(125); 10. bitset<32> bs3("101000101010"); 11. 12. cout << "bs1:" << bs1 << endl; 13. cout << "bs2:" << bs2 << endl; 14. cout << "bs3:" << bs3 << endl; 15. 16. return 0; 17. }
打印结果如下：
2.operator[ ]
返回下标位置的值：
bool operator[] (size_t pos) const;reference operator[] (size_t pos);
修改bs1第3位和第6位的值：
1. bs1[3] = 1; 2. bs1[6] = 1; 3. cout << "bs1:" << bs1 << endl;
3.count( )
返回位图对象中1的个数：
size_t count() const;
返回bs3中1的个数：
cout << bs3.count() << endl;
4.size( )
返回该位图对象的位数：
size_t size() const;
返回bs1、bs2、bs3的位数：
1. cout << "bs1:" << bs1.size() << endl; 2. cout << "bs2:" << bs2.size() << endl; 3. cout << "bs3:" << bs3.size() << endl;
5.test( )
返回该位在不在：
bool test (size_t pos) const;
返回bs2的每一位在不在：
1. cout << boolalpha;//把布尔值打印成true或false 2. for (size_t i = 0; i < bs2.size(); i++) 3. { 4. cout << bs2.test(i) << endl; 5. }
6.any( )
是否有至少1位为1：
bool any() const;
判断bs3是否至少有1位为1：
1. if (bs3.any()) 2. { 3. cout << "bs3至少有1位为1" << endl; 4. } 5. else 6. { 7. cout << "bs3没有1位为1" << endl; 8. }
7.none( )
是否全为0：
bool none() const;
判断bs3是否全为0：
1. if (bs3.none()) 2. { 3. cout << "bs3全为0" << endl; 4. } 5. else 6. { 7. cout << "bs3不全为0" << endl; 8. }
8.all( )
是否所有位都为1：
bool all() const noexcept;
判断bs3是否全为1：
1. if (bs3.all()) 2. { 3. cout << "bs3全为1" << endl; 4. } 5. else 6. { 7. cout << "bs3不全为1" << endl; 8. }
9.set( )
标记分以下两种：
1. bitset& set();//每个bit位都标记为1 2. bitset& set (size_t pos, bool val = true);//把第pos位标记为val
将bs4全标记为1 ，再将第6位标记为0，再将第6为标记为1：
1. bitset<16> bs4; 2. bs4.set(); 3. cout << bs4 << endl; 4. bs4.set(6,0); 5. cout << bs4 << endl; 6. bs4.set(6, 1); 7. cout << bs4 << endl;
10.reset( )
删除分为以下两种：
1. bitset& reset();//删除所有位，每一位都置为0 2. bitset& reset (size_t pos);//删除指定pos位，置为0
先删除bs5的第2位的标记 ，再删除所有位的标记：
1. bitset<16> bs5(0xFFFF); 2. cout << bs5 << endl; 3. bs5.reset(2); 4. cout << bs5 << endl; 5. bs5.reset(); 6. cout << bs5 << endl;
11.flip( )
取反分为以下两种：
1. bitset& flip();//全部取反 2. bitset& flip (size_t pos);//把第pos位取反
先对bs5的第2位取反，再对bs5全部取反：
1. bitset<16> bs5(0xFFFF); 2. cout << bs5 << endl; 3. bs5.flip(2); 4. cout << bs5 << endl; 5. bs5.flip(); 6. cout << bs5 << endl;
