[STL] BITSET
摘要
bitset<[an integer]> bs;
来定义一个 bitset。
bitset 可以像整数一样进行正常的位运算。
bitset 的长度固定。
bitset 的空间进行了优化,每位占 1bit。
bitset 的定义
// constructing bitsets
#include <iostream> // std::cout
#include <string> // std::string
#include <bitset> // std::bitset
int main ()
{
std::bitset<16> foo;
std::bitset<16> bar (0xfa2);
std::bitset<16> baz (std::string("0101111001"));
std::cout << "foo: " << foo << '\n';
std::cout << "bar: " << bar << '\n';
std::cout << "baz: " << baz << '\n';
return 0;
}
bitset 的相关函数
对于一个叫做 foo 的 bitset:
foo.size() 返回大小(位数)
foo.count() 返回 1 的个数
foo.any() 返回是否有 1
foo.none() 返回是否没有 1
foo.set() 全都变成 1
foo.set(p) 将第 p + 1 位变成 1
foo.set(p, x) 将第 p + 1 位变成 x
foo.reset() 全都变成 0
foo.reset(p) 将第 p + 1 位变成 0
foo.flip() 全都取反
foo.flip(p) 将第 p + 1 位取反
foo.to_ulong() 返回它转换为 unsigned long 的结果,如果超出范围则报错
foo.to_ullong() 返回它转换为 unsigned long long 的结果,如果超出范围则报错
foo.to_string() 返回它转换为 string 的结果
使用 bitset 来进行加法
即使用位运算来代替加法
假设有x+y
则carry=(x&y)<<1
为该加法的进位结果 sum=x^y
为该加法的非进位结果
显然carry+sum=x+y
则再对 carry 和 sum 进行重复操作
直到carry=0
。
Code
bs operator + (bs a, bs b) {
bs sum=a;
bs carry=b;
bs tmps;
while(carry.any()) {
tmps=sum;
sum=tmps^carry; // 求非进位结果
carry=(tmps&carry)<<1; // 求进位结果(两个相加等于最终结果)
}
return sum; // 进位结果等于0时,结束。
}
关于位运算时间复杂度
是个玄学。由于底层优化,初步推断接近 $O(1)$。可以应付 1e7 左右级别的修改操作?(由某题得出的结论,如果那题数据不水...)
然而常数还是比较大,因此慎用。
更正:复杂度一般认为是 $O(\frac{n}{32})$。在 O2 下有一定优化加持。
参考文章
胡小兔 - C++ bitset——高端压位卡常题必备 STL:https://www.cnblogs.com/RabbitHu/p/bitset.html
kiven.li - 用基本位运算实现加减乘除:https://www.cnblogs.com/kiven-code/archive/2012/09/15/2686922.html
本文链接:https://pst.iorinn.moe/archives/bitset.html
许可: https://pst.iorinn.moe/license.html若无特别说明,博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆