[STL] BITSET

ajcxsu
ajcxsu 2018年04月17日
  • 48 次阅读

摘要

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://acxblog.site/archives/bitset.html
本文采用 CC BY-NC-SA 3.0 协议进行许可