特殊容器之二进制有序集bitset

C++的bitset是一种类似数组的结构，它的每一个元素只能是０或１，每个元素仅用１bit空间。从整体效果来看，可以简单认为bitset中存放的就是一个无符号二进制整数。

一、bitset的定义和初始化

要使用bitset，首先需要引入头文件#include<bitset>。虽然bitset也是模板类，但是和vector很不同的是，定义bitset变量的基本格式：bitset<n> bs;，尖括号<>中是长度，并不是数据类型（bitset的元素只能是0或1，不存在数据类型一说）。

来看定义并初始化bitset的例子：

#include<iostream>
#include<bitset>
using namespace std;
int main()
{
	//没有参数，全部元素值为0 
	bitset<8> bs1;
	//bs1内容为{0,0,0,0,0,0,0,0} 
	
	//通过无符号整数初始化bitset
	//按无符号整数对应的二进制数的每一位来初始化bitset，高位补0 
	bitset<16> bs2(255);	//bitset(16) bs2(0xff);
	//255对应二进制11111111，二进制低位复制到bitset低位 
	//bs2内容为{1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0} 
	
	//通过01字符串（string或者char数组均可）初始化bitset
	string s = "1101001"; 
	bitset<10> bs3(s);		//bitset<10> bs3(string("1101001"));
	//字符串高位复制到bitset低位（因为字符串对应的二进制数的低位在字符串的高位） 
	//bs3内容为{1,0,0,1,0,1,1,0,0,0} 
	
	//直接用cout输出bitset（按对应二进制数的形式输出，输出时高位在前，低位在后） 
	cout<<bs1<<endl;	//00000000 
	cout<<bs2<<endl;	//0000000011111111 
	cout<<bs3<<endl;	//0001101001
	return 0;
}

可以通过无符号整数来初始化bitset，会将无符号整数对应的二进制数的低位到高位依次复制到bitset的低位到高位。也可以通过“01”字符串来初始化bitset，会将字符串逆序内容依次复制到bitset的低位到高位。初始化时，如果bitset长度够长，那么在bitset高位补0。如果bitset长度不够，对于用无符号整数来初始化bitset，会截取无符号整数对应二进制数的低位；对于用字符串来初始化bitset，会截取字符串的前面部分。

二、元素访问

可以像数组那样使用[]来获取bitset元素的值，也能对元素重新赋值，下标从0开始：

#include<iostream>
#include<bitset>
using namespace std;
int main()
{
	const int N = 16;
	bitset<N> bs(28);
	
	cout<<bs[0]<<" "<<bs[N-1]<<endl;
	cout<<bs<<endl;
	
	//正向遍历 
	for(int i=0;i<N;i++) cout<<bs[i];
	cout<<endl;
	
	//反向遍历 
	for(int i=N-1;i>=0;i--) cout<<bs[i];
	cout<<endl;
	
	bs[0] = bs[N-1] = 1;
	cout<<bs<<endl;
	return 0;
}

三、成员函数

四、位运算

前面提到，可以简单认为bitset中存放的就是一个无符号二进制整数。bitset内部还重载了几乎所有的位运算符，因此bitset也能像普通整数那样进行位运算：

#include<iostream>
#include<bitset>
using namespace std;
int main()
{
	bitset<8> bs1(string("10101101"));
	bitset<8> bs2(string("10100010"));
	
	//判断相等（支持==和!=运算） 
	if(bs1==bs2) cout<<"equal"<<endl;
	else cout<<"not equal"<<endl;
	
	//按位与运算 
	cout<<(bs1&bs2)<<endl;
	//按位或运算 
	cout<<(bs1|bs2)<<endl;
	//按位异或运算 
	cout<<(bs1^bs2)<<endl;
	//按位取反
	cout<<(~bs1)<<" "<<(~bs2)<<endl;
	
	//移位运算
	cout<<(bs1<<1)<<endl;	//左移，低位补0 
	cout<<(bs1>>2)<<endl;	//右移，高位补0
	
	//位运算并自赋值
	bs1 ^= bs2;
	cout<<bs1<<endl;
	bs1 >>= 3;
	cout<<bs1<<endl; 
	return 0;
}

五、经典例题

1.二进制十进制相互转换

需求：输出一个十进制数n转换为二进制。这里可以直接用十进制数初始化bitset，然后输出bitset即可（想办法不输出高位多余的0）。

#include<iostream>
#include<bitset>
using namespace std;
int main()
{
	int n;
	cin>>n;
	if(n<0) cout<<"-",n = -n;
	
	const int N = 32;
	bitset<N> bs(n);
	
	int i = N-1;
	//排除掉高位多余0 
	while(i>0 && !bs[i]) i--;
	
	for(;i>=0;i--) cout<<bs[i];
	return 0;
}

如何将二进制数转换成十进制呢？可以用“01”字符串初始化bitset，然后用成员函数to_ulong或者to_ullong来返回对应的无符号十进制数。

#include<iostream>
#include<bitset>
using namespace std;
int main()
{
	string s;
	cin>>s;
	bitset<64> bs(s);
	cout<<bs.to_ullong()<<endl; 
	return 0;
}

2.bitset作为标记数组

bitset的每个元素值只能是0或者1，占1个bit，可以将bitset用作标记“0-1”状态的“标记数组”，比起int数组要更节约存储空间。以前面的一个问题为例——数组例题——房间的门：

#include<iostream>
#include<bitset>
using namespace std;
int main()
{
	const int N = 100;
	bitset<N+1> bs;
	
	for(int i=1;i<=N;i++){
		for(int j=i;j<=N;j+=i){
			bs.flip(j);
		}
	}
	
	//门开着的房间的数量 
	cout<<bs.count()<<endl;
	//输出门开着的房间的编号 
	for(int i=1;i<=N;i++){
		if(bs.test(i)) cout<<i<<" ";
	}
	return 0;
}