c++ - 埃拉托色尼筛：按位优化

Question

在网上搜索后，我知道按位版本的eratosthenes 筛子非常有效。问题是我无法理解它使用的数学/方法。

我一直在忙的版本是这样的：

#define MAX 100000000
#define LIM 10000

unsigned flag[MAX>>6]={0};

#define ifc(n) (flag[n>>6]&(1<<((n>>1)&31)))         //LINE 1
#define isc(n) (flag[n>>6]|=(1<<((n>>1)&31)))        //LINE 2

void sieve() {
    unsigned i, j, k;
    for(i=3; i<LIM; i+=2)
        if(!ifc(i))
            for(j=i*i, k=i<<1; j<LIM*LIM; j+=k)
                isc(j);
}

我理解的要点（如果我错了，请纠正我）：

1. 第 1 行中的语句检查数字是否为复合数。
2. 第 2 行中的语句将数字“n”标记为复合数。
3. 该程序将值 0 或 1 存储在 int 的位中。这往往会将内存使用量减少到 x/32。（x 是使用 int 来存储 0 或 1 而不是像我上面的解决方案中那样的大小）

到目前为止，我脑海中的要点：

1. LINE 1 中的函数如何运作。确保数字是否为复合数的函数如何。
2. LINE 2 中的功能如何设置该位。
3. 我也开始知道按位筛在时间上也是有效的。是因为仅使用按位运算符还是其他原因也在起作用。

有什么想法或建议吗？

Answer 1

从技术上讲，代码中也存在一个错误：

无符号标志[MAX>>6]={0};

除以MAX64，但如果MAX不是 64 的精确倍数，则数组短一个元素。

第 1 行：让我们把它分开：

 (flag[n>>6]&(1<<((n>>1)&31)))

flag[n>>6] (n >> 6 = n / 64)给出 32 位整数，其中包含 的位值n / 2。

由于只有“奇数”是可能的素数，所以除以n二：(n>>1).

为我们1<<((n>>1)&31)提供了对应n/2于0..31- 的位（& 31确保它在“范围内”）。

最后，使用&将左边的值与右边的值结合起来。

因此，如果元素 for设置n了位数，则结果为真n modulo 32。

第二行本质上是相同的概念，只是它使用|=（或等于）设置倍数对应的位。