https://img-blog.csdnimg.cn/img_convert/2319540b52ba53f88ff0afbf5cabb92c.png#pic_center

bitset与埃氏筛

2022-02-22 约 2134 字预计阅读 5 分钟

bitset

介绍

std::bitset 是标准库中的一个存储 0/1 的大小不可变容器。严格来讲，它并不属于 STL。

bitset 并不属于 STL，而是一种标准库中的 “Special Container”。事实上，它作为一种容器，也并不满足 STL 容器的要求。说它是适配器，它也并不依赖于其它 STL 容器作为底层实现。——摘自《The C++ Standard Library 2nd Edition》

由于内存地址是按字节即 byte 寻址，而非比特 bit，一个 bool 类型的变量，虽然只能表示 0/1, 但是也占了 1 byte 的内存。

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

对于一个 4 字节的 int 变量，在只存 0/1 的意义下，bitset 占用空间只是其，计算一些信息时，所需时间也是其。

在某些情况下通过 bitset 可以优化程序的运行效率。至于其优化的是复杂度还是常数，要看计算复杂度的角度。一般 bitset 的复杂度有以下几种记法：（设原复杂度为）

$O(n)$，这种记法认为 bitset 完全没有优化复杂度。
$O(n/32)$，这种记法不太严谨（复杂度中不应出现常数），但体现了 bitset 能将所需时间优化至 $1/32$。
$O(n/w)$，其中 $w=32$（计算机的位数），这种记法较为普遍接受。
$O(n/logw)$，其中 $w$ 为计算机一个整型变量的大小。

当然，vector 的一个特化 vector<bool> 的储存方式同 bitset 一样，区别在于其支持动态开空间，bitset 则和我们一般的静态数组一样，是在编译时就开好了的。

然而，bitset 有一些好用的库函数，不仅方便，而且有时可以避免使用 for 循环而没有实质的速度优化。因此，一般不使用 vector<bool>。

使用¶

头文件¶

#include <bitset>

指定大小¶

bitset<1000> bs; // a bitset with 1000 bits

构造函数¶

bitset(): 每一位都是 false。
bitset(unsigned long val): 设为 val 的二进制形式。
bitset(const string& str): 设为串 str。

运算符¶

operator []: 访问其特定的一位。
operator ==/!=: 比较两个 bitset 内容是否完全一样。
operator &/&=/|/| =/^/^=/~: 进行按位与/或/异或/取反操作。bitset 只能与 bitset 进行位运算，若要和整型进行位运算，要先将整型转换为 bitset。
operator <>/<<=/>>=: 进行二进制左移/右移。
operator <>: 流运算符，这意味着你可以通过 cin/cout 进行输入输出。

成员函数¶

count(): 返回 true 的数量。
size(): 返回 bitset 的大小。
test(pos): 它和 vector 中的 at() 的作用是一样的，和 [] 运算符的区别就是越界检查。
any(): 若存在某一位是 true 则返回 true，否则返回 false。
none(): 若所有位都是 false 则返回 true，否则返回 false。
all():C++11，若所有位都是 true 则返回 true，否则返回 false。
1. set(): 将整个 bitset 设置成 true。
2. set(pos, val = true): 将某一位设置成 true/false。
1. reset(): 将整个 bitset 设置成 false。
2. reset(pos): 将某一位设置成 false。相当于 set(pos, false)。
1. flip(): 翻转每一位。（相当于异或一个全是 1 的 bitset）
2. flip(pos): 翻转某一位。
to_string(): 返回转换成的字符串表达。
to_ulong(): 返回转换成的 unsigned long 表达 (long 在 NT 及 32 位 POSIX 系统下与 int 一样，在 64 位 POSIX 下与 long long 一样）。
to_ullong():C++11，返回转换成的 unsigned long long 表达。

一些文档中没有的成员函数：

_Find_first(): 返回 bitset 第一个 true 的下标，若没有 true 则返回 bitset 的大小。
_Find_next(pos): 返回 pos 后面（下标严格大于 pos 的位置）第一个 true 的下标，若 pos 后面没有 true 则返回 bitset 的大小。

应用¶

「LibreOJ β Round #2」贪心只能过样例 ¶

这题可以用 dp 做，转移方程很简单：

表示前个数的平方和能否为，那么（或起来）。

但如果直接做的话是的，（看起来）过不了。

发现可以用 bitset 优化，左移再或起来就好了：std::bitset

然后发现……被加了几个剪枝的暴力艹了：加了几个剪枝的暴力

然而，可以手写 bitset（只需要支持左移后或起来这一种操作）压位（unsigned long long）来艹掉暴力：手写 bitset

与埃氏筛结合

由于 bitset 快速的连续读写效率（前提是开O2优化），使得它非常适合用于与埃氏筛结合打质数表。

使用的方式也很简单，只需要将埃氏筛中的布尔数组替换成 bitset 即可。

参考代码

bitset<N> vis;

void Prime(int n) {
  vis.set();
  vis[0] = vis[1] = 0;
  for (int i = 2; i * i <= n; i++) {
    if (vis[i]) {
      for (int j = i << 1; j <= n; j += i) vis[j] = 0;
    }
  }
}

埃氏筛速度测试

测试代码如下：

#include<cstdio>
#include "../BenchMark/Timer.h"
using namespace std;
#define BIT_SET		//通过是否定义BIT_SET宏来控制测试对象


#ifdef BIT_SET
#include<bitset>
 bitset<100001000> vis;
#else
bool vis[100001000];
#endif

int n, ans;


#ifdef BIT_SET
void Prime() {
   vis.set();
  vis[0] = vis[1] = 0;
  for (int i = 2; i * i <= n; i++) {
    if (vis[i]) {
      for (int j = i << 1; j <= n; j += i) vis[j] = 0;
    }
  }
}
#else
void GetPrimes() {
    fill(vis,vis+100001000, true);
    vis[0] = vis[1] = 0;
    for (int i = 2; i * i <= n; i++) {
        if (vis[i]) {
            for (int j = i << 1; j <= n; j += i) vis[j] = 0;
        }
    }
}
#endif

int main() {
    scanf("%d", &n);
    {
        ans = 0;
        Timer c;
        #ifdef BIT_SET
        Prime();
        #else
        GetPrimes();
        #endif
        for (int i = 2; i <= n; i++)
            if (vis[i])
                ans++;
        printf("%d  ", ans);
    }
    return 0;
}

其中的计时器Timer是我封装的一个用于测试速度的类，利用的C++ RAII特性写的。

代码如下：

//
// Created by Alone on 2022-1-31.
//

#ifndef BENCHMARK_TIMER_H
#define BENCHMARK_TIMER_H
#include <chrono>
#include <iostream>
class Timer {
public:
    Timer(){
         m_StartTimepoint = std::chrono::high_resolution_clock::now();
    }
    ~Timer(){
        Stop();
    }
    void Stop(){
        auto endTimepoint = std::chrono::high_resolution_clock::now();
        auto start = std::chrono::time_point_cast<std::chrono::microseconds>(m_StartTimepoint).time_since_epoch().count();
        auto end = std::chrono::time_point_cast<std::chrono::microseconds>(endTimepoint).time_since_epoch().count();
        auto duration = end-start;  //以微秒为单位
        double ms = duration * 0.001;//得到毫秒
        printf("%lld us (%lf ms)\n",duration,ms);
    }
private:
    std::chrono::time_point<std::chrono::high_resolution_clock>m_StartTimepoint;
};


#endif //BENCHMARK_TIMER_H

测试结果：

测试中使用的环境为mingw，使用了 $o2$ 级别的优化，所以 bitset 明显会快很多！

在 n==1e8 的情况下，轮番三次 bool vs bitset 结果如下：

第一次：1351532 us (1351.532000 ms) vs 1171797 us (1171.797000 ms)

第二次：1814639 us (1814.639000 ms) vs 1236894 us (1236.894000 ms)

第三次：1812811 us (1812.811000 ms) vs 5761455 1188555 us (1188.555000 ms)

难道以后都优先使用bitset？别高兴的太早！在我们默认的debug模式下bitset根本就完全不是bool数组的对手，随手一测，直接就是 2397002 us (2397.002000 ms) vs 8512716 us (8512.716000 ms) bitset大败！！！

所以，在一般的算法题情况下，写质数筛还是用bool数组吧！因为算法题的oj不会给你开优化的！故原始bool数组是最好的选择！

目录