bitset学习笔记

发表于 分类于 阅读次数： 评论数：
本文字数： 293 阅读时长 ≈ 1 分钟
本文记录了bitset的学习

cppreference about bitset

Introduction

C++的 bitset 在 \ 头文件中，它是一种类似数组的结构，它的每一个元素只能是0或１，每个元素仅用１bit空间。

常常碰到处理的数组只有0和1的变化，此时就可以使用bitset优化。比如求两个集合的交集可以使用按位与运算，求并集可以使用按位或运算

operator

构造函数

1
2
3
4
5
6
7
8
9
10
11
12
bitset<4> bitset1;//无参构造，长度为４，默认每一位为0
bitset<8> bitset2(12);//长度为８，二进制保存，前面用0补充
string s = "100101";
bitset<10> bitset3(s);//长度为10，前面用0补充
char s2[] = "10101";
bitset<13> bitset4(s2);//长度为13，前面用0补充
bitset<3> bitset5("1100011"); // 当位数不够时候，只取前面的
cout << bitset1 << endl;//0000
cout << bitset2 << endl;//00001100
cout << bitset3 << endl;//0000100101
cout << bitset4 << endl;//0000000010101
cout << bitset5 << endl;//110

修改器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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 (左移２位，低位补0，有自身赋值)
cout << (foo>>=1) << endl;        // 0110 (右移１位，高位补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 (按位异或，不赋值)

元素访问 test顺带检查了是否合法下标

1
2
3
4
5
//类似数组，通过[]访问，下标从0开始。也可以修改
bitset<4> foo ("1011");
cout << foo[0] << endl;　　//1
cout << foo[1] << endl;　　//1
cout << foo[2] << endl;　　//0

一些常用函数：

1
2
3
4
5
6
7
8
9
10
bitset<8> foo ("10011011");
cout << foo.count() << endl;　　//5　　（count函数用来求bitset中1的位数，foo中共有5个1
cout << foo.size() << endl;　　 //8　　（size函数用来求bitset的大小，一共有8位

cout << foo.test(0) << endl;　　//true　　（test函数用来查下标处的元素是0还是1，并返回false或true，此处foo[0]为1，返回true
cout << foo.test(2) << endl;　　//false　　（同理，foo[2]为0，返回false

cout << foo.any() << endl;　　//true　　（any函数检查bitset中是否有１
cout << foo.none() << endl;　　//false　　（none函数检查bitset中是否没有１
cout << foo.all() << endl;　　//false　　（all函数检查bitset中是全部为１

常见类型转换函数

1
2
3
4
5
6
7
bitset<8> foo ("10011011");
string s = foo.to_string();　　//将bitset转换成string类型
unsigned long a = foo.to_ulong();　　//将bitset转换成unsigned long类型
unsigned long long b = foo.to_ullong();　　//将bitset转换成unsigned long long类型
cout << s << endl;　　//10011011
cout << a << endl;　　//155
cout << b << endl;　　//155

  • set 将位置设置为1
  • reset 将位置设置为0
  • flip 翻转位，即更改 true 值为 false 并更改 false 值为 true 。等价于在 bitset 一部分或全体上的逻辑非。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
std::bitset<8> b;
for (size_t i = 1; i < b.size(); i += 2) {
    b.set(i);
}
std::cout << b << '\n';
/*10101010*/


std::bitset<4> b;
std::cout << b << "\n";
std::cout << b.flip(0) << '\n';
std::cout << b.flip(2) << '\n';
std::cout << b.flip() << '\n';
/*0000
0001
0101
1010*/

std::bitset<8> b(42);
std::cout << "Bitset is         " << b << '\n';
b.reset(1);
std::cout << "After b.reset(1): " << b << '\n';
b.reset();
std::cout << "After b.reset():  " << b << '\n';

/*Bitset is         00101010
After b.reset(1): 00101000
After b.reset():  00000000*/

函数汇总

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bitset<MAXN> bt; //  bt 包括 MAXN 位，下标 0 ~ MAXN - 1，默认初始化为 0 
bt.any()        //  bt 中是否存在置为 1 的二进制位？
bt.none()       //  bt 中不存在置为 1 的二进制位吗？
bt.count()      //  bt 中置为 1 的二进制位的个数
bt.size()       //  bt 中二进制位的个数
bt[pos]         //  访问 bt 中在 pos 处的二进制位
bt.test(pos)    //  bt 中在 pos 处的二进制位是否为 1
bt.set()        //  把 bt 中所有二进制位都置为 1
bt.set(pos)     //  把 bt 中在 pos 处的二进制位置为 1
bt.reset()      //  把 bt 中所有二进制位都置为 0
bt.reset(pos)   //  把 bt 中在pos处的二进制位置为0
bt.flip()       //  把 bt 中所有二进制位逐位取反
bt.flip(pos)    //  把 bt 中在 pos 处的二进制位取反
bt[pos].flip()  //  同上
bt.to_ulong()   //  用 bt 中同样的二进制位返回一个 unsigned long 值
os << bt        //  把 bt 中的位集输出到 os 流

题目

-------------本文结束感谢您的阅读-------------