跳转至

bitset

bitset :

介绍 :

std :: bitset是标准库中的一个固定大小序列, 其储存的数据只包含0/1

众所周知, 由于内存地址是按字节即byte寻址, 而非比特bit,

我们一个bool类型的变量, 虽然只能表示0/1, 但是也占了1byte的内存

bitset就是通过固定的优化, 使得一个字节的八个比特能分别储存 8 位的0/1

对于一个 4 字节的int变量, 在只存0/1的意义下, bitset占用空间只是其 \frac{1}{32}

在某些情况下通过bitset可以使你的复杂度除以 32

当然, vector的一个特化vector<bool>的储存方式同bitset一样, 区别在于其支持动态开空间,

bitset则和我们一般的静态数组一样, 是在编译时就开好了的.

那么为什么要用bitset而非vector<bool> ?

通过以下的介绍, 你可以更加详细的看到bitset具备的方便操作

1
#include <bitset>  // 包含 bitset 的头文件

运算符 :

  • operator[]: 访问其特定的一位

  • operator ==/!= : 比较两个bitset内容是否完全一样

  • operator &= / |= / ^= / ~ : 进行按位与 / 或 / 异或 / 取反操作

  • operator <</>> / <<= / >>= : 进行二进制左移 / 右移
  • operator <</>> : 流运算符, 这意味着你可以通过cin/cout进行输入输出

vector<bool>只具有前两项

成员函数 :

  • test(): 它和vector中的at()的作用是一样的, 和[]运算符的区别就是越界检查
  • count(): 返回true的数量
  • set(): 将整个bitset设置成true, 你也可以传入参数使其设置成你的参数
  • reset(): 将整个bitset设置成false
  • flip(): 翻转该位 (0 变 1,1 变 0), 相当于逻辑非 / 异或 1
  • to_string(): 返回转换成的字符串表达
  • to_ulong(): 返回转换成的unsigned long表达 (long在 NT 及 32 位 POSIX 系统下与int一样, 在 64 位 POSIX 下与long long一样)
  • to_ullong() C++11, 返回转换成的unsigned long long表达

这些vector<bool>基本都没有

作用 :

一般来讲, 我们可以用bitset优化一些可行性 DP, 或者线筛素数 (notprime这种bool数组可以用bitset开到 10^8 之类的)

它最主要的作用还是压掉了内存带来的时间优化, \frac{1}{32} 的常数优化已经可以是复杂度级别的优化了, 比如一个 N = 1000 O(N^3) 算法, 10^9 显然很卡, 在常数大一点的情况下必然卡不过去,O(松) 不能算!!!!, 这时候如果我们某一维除以 32, 则可以比较保险的过了这道题

其实bitset不光是一个容器, 更是一种思想, 我们可以通过手写的方式, 来把long long什么的压成每 bit 表示一个信息, 用 STL 的原因更多是因为它的运算符方便


评论