众所周知\(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 用来查下标处的元素是0还是1
s.test(2) //false 同理,s[2]为0,返回false
s.any() //true any函数检查bitset中是否有1
s.none() //false none函数检查bitset中是否没有1
s.all() //false all函数检查bitset中是全部为1
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 (左移2位,低位补0,有自身赋值)
s>>=1 //0110 (右移1位,高位补0,有自身赋值)
~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 (按位异或,不赋值)
标签:bar,函数,用法,按位,bitset,false,Bitset,赋值
From: https://www.cnblogs.com/Diamondan/p/17592658.html