【c++STL——第十讲】bit set系列 (常用知识点总结)

ฅ(๑˙o˙๑)ฅ 大家好, 欢迎大家光临我的博客：面向阿尼亚学习
算法学习笔记系列持续更新中~

• 一、前言
• 二、bit set的定义
• 三、bit set的基本运算
• 四、bit set的常用函数
• 五、bit set的作用
• 最后

在 C++ 中，严格来说，bitset并不属于stl容器的范畴，它也不支持指示器的操作。bitset提供了对数据的位操作。

bit set 压位
即如其名,bit set储存的是二进制。

它是一种类似数组的结构，它的每一个元素只能是０或１，每个元素仅用１bit空间,用于节省空间，
并且可以直接用01串赋值，可以理解为一个二进制的数组

 #include   // 包含 bitset 的头文件

 bitset  变量名；
 //表示一个n位的二进制数，<>中填写位数；
 
 如：
 bitset<4> b;　　//无参构造，长度为４，默认每一位为０

 string s = "100101"; //01串赋值
 bitset<10> b(s);　　//长度为10，前面用０补充
 //或者 bitset<10> b("100101")
      
 bitset<10> b[10];//开了b[10]个长度为10的二进制数
      

bitset也可以当作布尔类型的数组来使用

如果执行如下语句：

bitset<8> b;

b[1]=1;

cout<

那么可以得到00000010。bitset每位只占一个字节，空间性能非常优秀。

​

 
  支持：


    ~s: 返回对s每一位取反后的结果；
    
    &，|，^：返回对两个位数相同的bitset执行按位与、或、异或运算的结果；

​    >>，<<：返回把一个bitset左移，右移若干位的结果.（补零）；

​    ==，!=
        
    [k] :表示s的第k位，即可取值也可赋值，编号从0开始；
        

样例代码：
位运算操作优先级很低，记得括号是必须要加的。

#include 
#include
using namespace std;
int main() {

	bitset<4> a("0101");

	bitset<4> b("1110");

	cout<<(a&b)< 
输出结果：
 0100
 1111
 1011
 1010
 0001
 
四、bit set的常用函数 
​    count(); 返回某一个数的个数
// s.count() 返回二进制串中有多少个1；

​    any(); 判断是否至少有一个1
​    none(); 判断是否全为0
// 若s所有位都为0，则s.any()返回false，s.none()返回true；
// 若s至少有一位为1，则s.any()返回true，s.none()返回false；

​    set(); 把所有位置赋值为1

​    set(k,v); 将第k位变成v
//s.set()把s所有位变为1；
//s.set(k,v)把s的第k位改为v,即s[k]=v；

​    reset(); 把所有位变成0
//s.reset()把s的所有位变为0.
//s.reset(k)把s的第k位改为0,即s[k]=0；

​    flip(); 把所有位取反，等价于~
//s.flip()把s所有位取反.即s=~s；
//s.flip(k)把s的第k位取反，即s[k]^=1；
        
    to_string() 返回转换成的字符串表达
        
    to_ulong() 返回转换成的 unsigned long 表达 
                                      
    to_ullong() C++11, 返回转换成的 unsigned long long 表达
        

 
 
五、bit set的作用 
一般来讲，我们可以用 bitset 优化一些可行性 DP, 或者线筛素数 ( notprime 这种 bool 数组可以用 bitset ）
 
它最主要的作用还是压掉了内存带来的时间优化， 的常数优化已经可以是复杂度级别的优化了，比如一个 的 算法， 显然很卡，在常数大一点的情况下必然卡不过去，O（松）不能算！, 这时候如果我们某一维除以 32, 则可以比较保险的过了这道题
 
原因
 
 
 
众所周知，由于内存地址是按字节即 byte 寻址，而非比特 bit ,
 我们一个 bool 类型的变量，虽然只能表示 0/1 , 但是也占了 1byte 的内存
 bitset 就是通过固定的优化，使得一个字节的八个比特能分别储存 8 位的 0/1
 对于一个 4 字节的 int 变量，在只存 0/1 的意义下， bitset 占用空间只是其
 在某些情况下通过 bitset 可以使你的复杂度除以 32
 
 
其实 bitset 不光是一个容器，更是一种思想，我们可以通过手写的方式，来把 long long 什么的压成每 bit 表示一个信息，用 STL 的原因更多是因为它的运算符方便
 
最后 
莫言真理无穷尽，寸进自有寸进欢