为何位集（bitset）操作比数组操作更快？——C语言埃拉托斯特尼筛法中的性能提升疑惑

兄弟，你的这个发现真的挺有意思！我来给你掰扯掰扯为啥位集版本的筛法会比bool数组版本更快～

核心原因：缓存与内存带宽的双重优化 #

这是性能提升的关键，主要体现在两个方面：

• 缓存命中率暴增：你用bool数组的时候，每个标记至少占1个字节（C标准里bool通常是1字节大小），筛到1亿的话，数组得占100MB左右。而位集版本每个标记只占1位，同样的规模只需要12.5MB——体积直接缩到原来的1/8！CPU的缓存空间是有限的（比如L3缓存一般也就几十MB），位集能更充分地“住”进缓存里，减少CPU去内存里捞数据的次数。内存访问可比缓存慢好几个数量级，这部分时间省下来就非常可观。
• 内存带宽利用率更高：CPU读取内存是按「缓存行」（通常64字节）来批量读取的。bool数组一个缓存行只能装64个标记，而位集一个缓存行能装64×8=512个标记！同样的内存带宽，位集能一次性处理8倍的数据，效率自然上去了。

位运算的额外开销几乎可以忽略 #

你可能会担心：位集操作需要额外的移位、按位与/或这些运算，会不会拖慢速度？其实完全不用怕——现代CPU有专门优化的位运算指令，处理这些操作快得飞起。而且很多位集实现还会用批量操作的技巧（比如一次处理多个字节的位），反而能抵消掉这些额外开销，甚至比数组的单字节操作更高效。

附上两种版本的核心代码参考 #

bool数组版本

#include <stdbool.h>
#include <stdlib.h>

void sieve_array(int limit) {
    bool *is_prime = malloc(sizeof(bool) * (limit + 1));
    if (!is_prime) return;
    
    // 初始化所有位为true
    for (int i = 0; i <= limit; i++) {
        is_prime[i] = true;
    }
    is_prime[0] = is_prime[1] = false;
    
    // 埃拉托斯特尼筛法核心逻辑
    for (int p = 2; p * p <= limit; p++) {
        if (is_prime[p]) {
            for (int i = p * p; i <= limit; i += p) {
                is_prime[i] = false;
            }
        }
    }
    
    // 后续统计质数数量或清理资源
    free(is_prime);
}

位集版本

#include <stdlib.h>

// 位集操作宏定义
#define BITSET_SIZE(n) ((n + 7) / 8)
#define SET_BIT(bits, i) ((bits)[(i)/8] |= (1 << ((i)%8)))
#define CLEAR_BIT(bits, i) ((bits)[(i)/8] &= ~(1 << ((i)%8)))
#define TEST_BIT(bits, i) ((bits)[(i)/8] & (1 << ((i)%8)))

void sieve_bitset(int limit) {
    unsigned char *bits = malloc(BITSET_SIZE(limit + 1));
    if (!bits) return;
    
    // 初始化所有位为1（表示质数）
    for (int i = 0; i < BITSET_SIZE(limit + 1); i++) {
        bits[i] = 0xFF;
    }
    CLEAR_BIT(bits, 0);
    CLEAR_BIT(bits, 1);
    
    // 埃拉托斯特尼筛法核心逻辑
    for (int p = 2; p * p <= limit; p++) {
        if (TEST_BIT(bits, p)) {
            for (int i = p * p; i <= limit; i += p) {
                CLEAR_BIT(bits, i);
            }
        }
    }
    
    // 后续统计质数数量或清理资源
    free(bits);
}

备注：内容来源于stack exchange，提问作者Lemma