Bitset用法

Diamondan / 2023-07-31 / 原文

众所周知\(Bitset\)可以将一些\(O(n)\)的操作优化为\(O(N/w)\)
相当于优化了\(>=\)一只\(log\)!!!

\(bitset\)每一位占一个\(bit\)，而不是一个\(Byte\)!!!
若一次操作复杂度为 \(O(N)\)
\(bitset\)的操作复杂度为 \(O(N/w)\) \(w\)为计算机字长，\(w\)位系统字长为\(w\)
相比之下，空间也更优，为\(O(N/w)\)

\(Warning:\)标号与对应顺序相反

如 11110111 对应 标号76543210

一些函数

询问函数

  bitset<8> s("10011011"); //用字符串直接赋值 8为大小
  s.count()  //5　　求bitset中1的位数
  s.size()   //8　　求bitset的大小

  s.test(0)  //true   用来查下标处的元素是０还是１
  s.test(2)  //false　 同理，s[2]为０，返回false

  s.any()　　 //true　　 any函数检查bitset中是否有１
  s.none()   //false　　none函数检查bitset中是否没有１
  s.all()    //false　　all函数检查bitset中是全部为１

  s.flip(x)  //将x标号对应的数取反
  s.flip()   //全取反

赋值函数

  bitset<N> s; //s大小为N
  s.reset(x) //将x赋值为0
  s.reset()  //全不重置为0
  s.set(x)   //将x赋值为1
  s.set()    //全不重置为1
  s[i]=1     //将bitset的第i位标记为1

转型函数

  s.to_string() //将bitset转换成string类型
  s.to_ulong    //将bitset转换成ul类型  长度不超过log(MAX_ul)
  s.to_ullong   //将bitset转换成ull类型 长度不超过log(MAX_ull)

\(Warning:\)\(bitset\)可以按位进行位运算
如：

      bitset<4> s(string("1001"));
      bitset<4> bar(string("0011"));
      s^=bar       //1010 (s对bar按位异或后赋值给s)
      s&=bar       //0010 (按位与后赋值给s)
      s|=bar       //0011 (按位或后赋值给s)
      s<<=2        //1100 (左移２位，低位补０，有自身赋值)
      s>>=1        //0110 (右移１位，高位补０，有自身赋值)
      ~bar         //1100 (按位取反)
      bar<<1       //0110 (左移，不赋值)
      bar>>1       //0001 (右移，不赋值)
      s==bar       //false (0110==0011为false)
      s!=bar       //true  (0110!=0011为true)
      s&bar        //0010 (按位与，不赋值)
      s|bar        //0111 (按位或，不赋值)
      s^bar        //0101 (按位异或，不赋值)