摘要

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