bitset详解

大家好，欢迎来到IT知识分享网。

主页面目录

10 bitset

10.1 介绍

bitset 在 bitset 头文件中，它类似数组，并且每一个元素只能是０或１，每个元素只用１bit空间

//头文件 #include<bitset> 

10.2 初始化定义

初始化方法

注意：n必须为常量表达式

演示代码：

#include<bits/stdc++.h> using namespace std; int main() { 
    // 1 无参构造 bitset<4> bitset1; //无参构造，长度为４，默认每一位为０ // 2 有参构造：数字作为参数 bitset<9> bitset2(12); //长度为9，将该数转化为二进制保存，前面用０补充 // 或此写法 bitset<9> bitset2({12}); // 3 有参构造：string字符串作为参数  string s = ""; bitset<10> bitset3(s); //长度为10，前面用 0 补充 // 4 有参构造：char字符数组（字符串）作为参数  char s2[] = "10101"; bitset<13> bitset4(s2); //长度为13，前面用 0 补充 cout << bitset1 << endl; //0000 cout << bitset2 << endl; //000001100 cout << bitset3 << endl; //0000 cout << bitset4 << endl; //0000000010101 return 0; } 

10.3 特性

bitset可以进行位操作

bitset<4> foo (string("1001")); bitset<4> bar (string("0011")); cout << (foo ^= bar) << endl;// 1010 (foo对bar按位异或后赋值给foo) cout << (foo &= bar) << endl;// 0001 (按位与后赋值给foo) cout << (foo |= bar) << endl;// 1011 (按位或后赋值给foo) cout << (foo <<= 2) << endl;// 0100 (左移2位，低位补0，有自身赋值) cout << (foo >>= 1) << endl;// 0100 (右移1位，高位补0，有自身赋值) cout << (~bar) << endl;// 1100 (按位取反) cout << (bar << 1) << endl;// 0110 (左移，不赋值) cout << (bar >> 1) << endl;// 0001 (右移，不赋值) cout << (foo == bar) << endl;// false (1001==0011为false) cout << (foo != bar) << endl;// true (1001!=0011为true) cout << (foo & bar) << endl;// 0001 (按位与，不赋值) cout << (foo | bar) << endl;// 1011 (按位或，不赋值) cout << (foo ^ bar) << endl;// 1010 (按位异或，不赋值) 

访问

//可以通过 [] 访问元素(类似数组)，注意最低位下标为0，类似于数的二进制表示，如下： bitset<4> f("1011"); for (int i = 0; i < 4; ++i) { 
     cout << f[i]; } // 输出1101 

注意： bitset访问时候是从右边（最低位）开始访问的，但是左右移位的时候还是按照原来的形式左右移位的

10.4 方法函数

10.5 bitset优化

一般会使用bitset来优化时间复杂度，大概时间复杂度会除64或32，例如没有优化的时间复杂度为 $O(NM)$ ，使用bitset优化后复杂度可能就为 $O(\frac{NM}{64})$

bitset还有开动态空间的技巧，bitset常用在01背包优化等算法中

// 动态长度bitset实现 const int N = 1e6 + 5; // 开空间的上限，一般为数据范围附近的值 template <int len = 1> void bitset_(int sz) { 
      // sz即为想要开的大小 if (len < sz) { 
      bitset_<min(len * 2, N)>(sz); return; } bitset<len + 1> dp; // 具体算法的实现 }