bitset

[Ir1d]

https://oi-wiki.org/ds/stl/bitset/

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛竞赛

[sshwy]

@yzy-1 欢迎pr～

[zerc7]

stl 要吸氧（问题已解决

Emm,关于 bitset 与埃氏筛结合的速度测试哪里有点问题.

起因是：luogu P3912 N <= 10^8

我用埃氏筛+bitset 一直 TLE，最后用 bool 数组才 AC

然后我在本地测试发现在 n = 100000000 下，bool 数组约2s，bitset 约10s（虽说电脑比较渣，但是差距有点太大了

luogu AC code && 记录

测试代码：

#include<cstdio>
#include<bitset>
#include<ctime>
using namespace std;
// bitset<100001000> vis;
bool vis[100001000];
double st, ed;
int n, ans;
void GetPrimes() {
    for (int i = 2; i * i <= n; i++) {
        if (vis[i]) continue;
        for (int j = i; j <= n / i; j++) 
            vis[i*j] = 1;
    }
}
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;
    }
  }
}
int main() {
    scanf("%d", &n);
    st = clock();
    GetPrimes();
    // Prime();
    for (int i = 2; i <= n; i++)
        if (!vis[i])
            ans++;
    printf("%d", ans);
    ed = clock();
    printf("\n\n%lf\n", (ed - st) / 1000.0);
    return 0;
}

[Youngchen2022]

似乎bitset单个修改速度是O(n/w)的（相当于速度平方了），但信息源不可靠（

[CoderOJ]

@zerc7

Emm,关于 bitset 与埃氏筛结合的速度测试哪里有点问题.

stl 要速度快基本都要开 O2 的

[zerc7]

@CoderOJ
@zerc7

Emm,关于 bitset 与埃氏筛结合的速度测试哪里有点问题.

stl 要速度快基本都要开 O2 的

啊这啊这[捂脸哭]

[CoelacanthusHex]

@zerc7 c++ 的非 O2 O3 基本上是 debug 用的，不会有人在生产环境跑 O1 和 O0

[missingroom]

多次测试，欧拉筛使用bitset优化也显著快于bool数组

n=1e8时，bitset约为500ms，bool数组约为600ms

测试环境是洛谷在线IDE（C++20，O2）

测试代码：

void Prime() {
    for(int i=2;i<=n;i++){
        if(!vis[i]) Pr.push_back(i);
        for(int j:Pr){
            if(i*j>n) break;
            vis[i*j]=1;
            if(i%j==0) break;
        }
    }
}

不过这种数据范围bitset比bool数组快是必然的吧，bitset占的空间比数组小多了

[383494]

是吸氧的原因吗

[xizhiwai]

真的会负优化吗，我在洛谷上欧拉筛+bitset比bool数组要快https://www.luogu.com.cn/problem/P3383

[shenpengfii]

【附注】bitset 二进制由低位至高位存储！

以数字 8 为例，其二进制为 1000, 在 bitset 中按顺序存储为 {0, 0, 0, 1}.