浅析|浅析 c++ bitset 的用法
浅析 c++ bitset 的用法
总述
C++的 \(bitset\) 位于
头文件中,这是一种类似于数组的数据结构,每个位置存储 \(0\ or\ 1\) ,并且每个元素仅用 \(1\ bit\) 的空间
如果换一种方式来想,\(bitset\) 就是一个封装了一堆奇奇怪怪操作并支持状态压缩的 \(bool\) 数组,而且支持基本的位运算
定义 or 声明
bitset<4> bitset1;
//无参构造,长度为4,默认每一位为0
bitset<8> bitset2(12);
//长度为8,二进制保存,前面用0补充/*用string对象初始化bitset*/
string s = "100101";
bitset<10> bitset3(s);
//长度为10,前面用0补充/*用char对象初始化bitset*/
char s2[] = "10101";
bitset<13> bitset4(s2);
//长度为13,前面用0补充bitset<2> bitset5(12) //12的二进制为1100(长度为4),但bitset1的size=2,只取后面部分,即00cout << bitset1 << endl;
//0000
cout << bitset2 << endl;
//00001100
cout << bitset3 << endl;
//0000100101
cout << bitset4 << endl;
//0000000010101
cout << bitset5 << endl;
//00
需要注意的是:在用
string
去初始化的时候,string
中的字符只能为 \(0\ or\ 1\)操作 1.运算
与 位操作符 的用法相同
bitset<4> foo (string("1001"));
bitset<4> bar (string("0011"));
cout << (foo^=bar) << endl;
// 1010 (foo对bar按位异或后赋值给foo)
cout << (foo&=bar) << endl;
// 0010 (按位与后赋值给foo)
cout << (foo|=bar) << endl;
// 0011 (按位或后赋值给foo)cout << (foo<<=2) << endl;
// 1100 (左移2位,低位补0,有自身赋值)
cout << (foo>>=1) << endl;
// 0110 (右移1位,高位补0,有自身赋值)cout << (~bar) << endl;
// 1100 (按位取反)
cout << (bar<<1) << endl;
// 0110 (左移,不赋值)
cout << (bar>>1) << endl;
// 0001 (右移,不赋值)cout << (foo==bar) << endl;
// false (0110==0011为false)
cout << (foo!=bar) << endl;
// true(0110!=0011为true)cout << (foo&bar) << endl;
// 0010 (按位与,不赋值)
cout << (foo|bar) << endl;
// 0111 (按位或,不赋值)
cout << (foo^bar) << endl;
// 0101 (按位异或,不赋值)
2.访问
可以通过访问数组下标的形式访问 \(bitset\) 中的元素,注意最低位下标为 \(0\)
同时,也可以通过这种方式进行单点修改
bitset<4> foo ("1011");
cout << foo[0] << endl;
//1
cout << foo[1] << endl;
//1
cout << foo[2] << endl;
//0
cout << foo[3] << endl;
//1
3.一些函数的使用
bitset<1000> s;
s.count();
//返回s中1的个数s.any();
//当s全为0时,返回false;如果有任何一位为1,则返回true
s.none();
//当s全为0时,返回true;如果有任何一位为1,则返回falses.set();
//将s中每一位都设置为1
s.set(3,0);
//将s中第3位的数值设置为0
s.set(3);
//将s中第3位的数值设置为1s.reset();
//将s中每一位都设置为0
s.flip();
//对s中每一位都取反
需要注意的是
s.reset()
和 s.flip()
也可以传参数,和 s.set
的用法大致相同4.一些操作
对于一类题,有这样的书写方式
s |= s << w[i]
这句代码实际上是将 \(s\) 左移了 \(w[\ i\ ]\) 位,并且与原来的 \(s\) 取并集
下面拿两道例题举举栗子
Luogu P2347 [NOIP1996 提高组] 砝码称重
#include
using namespace std;
int w[10]={0,1,2,3,5,10,20},a[10];
bitset<1010> s;
int main(){
for(int i=1;
i<=6;
i++)
cin>>a[i];
s[0]=1;
for(int i=1;
i<=6;
i++)
for(int j=0;
j
Luogu P1441 砝码称重
#include
using namespace std;
const int N=2010;
int a[50],n,m,ans;
inline int read(){
int f=1,x;
char ch;
while((ch=getchar())<'0'||ch>'9') if(ch=='-') f=-1;
x=ch-'0';
while('0'<=(ch=getchar())&&ch<='9') (x*=10)+=ch-'0';
return x*f;
}inline int cal(unsigned int x){
int ret=0;
while(x!=0){
if(x&1) ret++;
x>>=1;
}
return ret;
}int main(){
n=read(),m=read();
for(int i=0;
i s;
s[0]=1;
for(int j=0;
j
这两个题在对可以称出的质量进行统计的时候使用了这个小技巧,就可以摆脱 \(dfs+dp\) 的复杂方式,从而转化为 \(bitset\) 的一道题目,大大优化了时间复杂度和空间复杂度
【浅析|浅析 c++ bitset 的用法】
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 浅析Redis基础数据结构
- C++编辑距离(动态规划)
- C++非继承时函数成员访问属性和类继承过程中的访问控制
- C语言|推荐一些嵌入式、C/C++的开源库和项目
- C/C++开源库|日志系统模块基础、C语言实现一个日志模块、zlog日志模块基础
- 理论知识|嵌入式应用的超轻量级、高性能的 C/C++ 日志库
- C++工厂方法之对象创建型模式详解
- c++和python实现顺序查找实例
- 详解C++中OpenSSL动态链接库的使用
- C++实现数独快速求解