bitset简单来说就是一个bit数组，和java里面的bitmap类似。
这次简单分析一下bitset以及它的应用。
目录
一.c++中bitset的使用
二.bitset的简单实现
三.bitset的应用
一.c++中bitset的使用
就用一段代码来说明，使用很简单。
#include <bitset>
#include <iostream>
int main()
{
std::bitset<10>bit("0000000001"); /* 可用字符串初始化,尖括号指定bit位数 */
std::cout << bit << std::endl;
bit[1] = 1; /* 和数组使用方式一样 */
std::cout << bit << std::endl;
std::cout << "bit[1]:" << bit[1] << std::endl;
std::cout << "test:" << bit.test(1) << std::endl; /* 类似bit[1] */
std::cout << "count:" << bit.count() << std::endl; /* 计算使用过的bit位*/
std::cout << "size:" << bit.size() << std::endl;
std::cout << "any:" << bit.any() << std::endl; /* 测试是否有bit被修改过 */
std::cout << "none:" << bit.none() << std::endl; /* 测试是否所有bit没有被修改过*/
std::cout << "all:" << bit.all() << std::endl; /* 测试所有bit是否被修改过 */
std::cout << "to_string:" << bit.to_string() << std::endl; /* 转成string类型 */
std::cout << "to_ulong:" << bit.to_ulong() << std::endl; /* 转成ulong类型 */
std::cout << "to_ullong:" << bit.to_ullong() << std::endl; /* 转成ullong类型*/
}
二.bitset的简单实现
源自编程珠玑的第一章第二题，让我们通过&，|，>>来实现bit数组。
* 定义一个整型的数组，每一位
* 代表一个bit*/
#include <iostream>
#define BitTegrSize (sizeof(int)*8)
#define N 10000000 /* 1000W数据 */
int main()
{
unsigned int array[1+N/BitTegrSize]; /* 开多大的数组 */
unsigned int a[2] = {0, 0}; /* 测试 */
std::cout << sizeof(int) << std::endl;
a[33>>5] |= (1 << ((33&0x1f)-1));
std::cout << a[1] << std::endl;
std::cout << (a[0] | 1) << std::endl;
int b = 0;
std::cout << (b | 1) << std::endl;
}代码中假设是用unsigned int 型数组来实现的（实际上内部是用什么类型实现的不一定，这里只是举例子，vs早期有用unsigned int来实现）
a[33>>5] |= (1 << ((33&0x1f)-1)); 将指定位设置为1,这里是设置a[33]
重点说说这个：33>>5等价于33/32，unsigned int 是32位，含义是定位到该bit所在的元素中，|= 与运算就是修改某一位为1，
(33&0x1f) 是通过&取余运算，且只能针对2^n的数取余。
解释一下这个0x1f是16进制的31，转化为2进制就是11111111，为什么取余32等于&31呢?
这个其实很好理解，比如x%y，余数最大就是y-1，所以在x转化为2进制代码中的数值我只关心它的起始的那几位即可 ，至于是几位就和y有关系了，比如
y等于16，那么最大余数是15，我就只关心起始5位，例如：x为10101000101010100001101，我就只关心红色几位数值即可，它们就是余数，&运算只是
把它们提取出来。（注意前面说了值针对2^n,原因是二进制呗！）
同理清除为1的指定位也就简单了。
三.bitset的应用
两个例子
1.某区有7位电话号码若干（千万级别），要求对其排序，占用内存要求在1MB左右。
大概算一下，8位电话号码也就是0000000-9999999，数值一共不到1千万吧，用unsigned即可。
那么加载进内存越为4*10000000字节，约等于40MB，如果我们用排序只能用归并排序了，至少也40次了吧，先不说次数多少，就磁盘IO来说就慢的不行了。
此时可以考虑bitset了，既然电话号码是连续的且不重复的，我们可以用bitset的bit下标来表示电话号码，比如1234567，就是bit[1234567]。那么好办了，
首先计算一下bitset需要的大概是40MB/32，也就是1MB左右，复合情况，我们可以直接遍历一遍，存在的号码S我们设置b[S]位为1，不存在则为0。
那么输出排序直接遍历bitset即可。节省空间且速度快^_^。
2. 2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。
这次用两个位表示一个数，00表示未出现过，01表示出现立了1次，11表示出现重复了。
遍历即可