NOIP学习小站
西安交通大学附属中学航天学校

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

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

一、bitset的定义和初始化

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

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

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#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;
}
#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; }
#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开始:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#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;
}
#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; }
#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;
}

三、成员函数

成员函数功能
bs.any()是否存在值为1的二进制位
bs.none()是否不存在值为1的二进制位(或者说,是否全部二进制位都为0)
bs.size()位长,也就是初始化时指定的长度(返回值类型是size_t)
bs.count()二进制位值为1的个数
bs.test(pos)测试pos处的二进制位是否为1
bs.set()全部二进制位的值设置为1
bs.set(pos)pos位处的二进制位的值设置为1
bs.set(pos,v)pos位处的二进制位的值设置为v
bs.reset()全部二进制位的值设置为0
bs.reset(pos)pos位处的二进制位的值设置为0
bs.flip()全部二进制位的值取反
bs.flip(pos)pos处的二进制位的值取反
bs.to_ulong()返回将二进制转换为unsigned long的结果
bs.to_ullong()返回将二进制转换为unsigned long long的结果
bs.to_string()返回将二进制转换为字符串的结果

四、位运算

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

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#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;
}
#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; }
#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)。

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#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;
}
#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; }
#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来返回对应的无符号十进制数。

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#include<iostream>
#include<bitset>
using namespace std;
int main()
{
string s;
cin>>s;
bitset<64> bs(s);
cout<<bs.to_ullong()<<endl;
return 0;
}
#include<iostream> #include<bitset> using namespace std; int main() { string s; cin>>s; bitset<64> bs(s); cout<<bs.to_ullong()<<endl; return 0; }
#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数组要更节约存储空间。以前面的一个问题为例——数组例题——房间的门

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
#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;
}
#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; }
#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;
}