Eratosthenes的筛子--位优化问题。

Question

我想每个人都遇到过Eratosthenes筛子的优化代码，有位操作。我正在尝试着去理解它，我对这个实现中的一个操作有疑问。下面是GeeksforGeeks的代码。

bool ifnotPrime(int prime[], int x) { 
    // checking whether the value of element 
    // is set or not. Using prime[x/64], we find 
    // the slot in prime array. To find the bit 
    // number, we divide x by 2 and take its mod 
    // with 32. 
    return (prime[x / 64] & (1 << ((x >> 1) & 31))); 
} 

// Marks x composite in prime[] 
bool makeComposite(int prime[], int x) { 
    // Set a bit corresponding to given element. 
    // Using prime[x/64], we find the slot in prime  
    // array. To find the bit number, we divide x 
    // by 2 and take its mod with 32. 
    prime[x / 64] |= (1 << ((x >> 1) & 31)); 
} 

// Prints all prime numbers smaller than n. 
void bitWiseSieve(int n) { 
    // Assuming that n takes 32 bits, we reduce 
    // size to n/64 from n/2. 
    int prime[n / 64]; 

    // Initializing values to 0 . 
    memset(prime, 0, sizeof(prime)); 

    // 2 is the only even prime so we can ignore that 
    // loop starts from 3 as we have used in sieve of 
    // Eratosthenes . 
    for (int i = 3; i * i <= n; i += 2) { 

        // If i is prime, mark all its multiples as 
        // composite 
        if (!ifnotPrime(prime, i)) 
            for (int j = i * i, k = i << 1; j < n; j += k) 
                makeComposite(prime, j); 
    } 

    // writing 2 separately 
    printf("2 "); 

    // Printing other primes 
    for (int i = 3; i <= n; i += 2) 
        if (!ifnotPrime(prime, i)) 
            printf("%d ", i); 
} 

// Driver code 
int main() { 
    int n = 30; 
    bitWiseSieve(n); 
    return 0; 
} 

我的问题是：

1. 什么是... (prime[x/64] & (1 << ((x >> 1) & 31)) 具体来说 (1 << ((x >> 1) & 31));
2. 在 prime[x/64] 为什么要除以 64 而不与 32当我们使用32位整数时。
3. 是 int prime[n/64] 对不对 n < 64?

Answer 1

代码中存在多个问题。

• makeComposite() 应该有返回类型 void.
• (1 << ((x >> 1) & 31)) 在以下情况下具有未定义的行为 x == 63 因为 1 << 31 溢出类型范围 int. 你应该使用 1U 或最好 1UL 以确保32位。
• 更简单的做法是将表项移位并屏蔽最后一位。return (prime[x / 64] >> ((x >> 1) & 31)) & 1;
• 而不是假设那个类型 int 有32位，你应该使用 uint32_t 作为位数组的类型。
• 该数组 int prime[n / 64]; 太短，如果 n 不是64的倍数。使用 uint32_t prime[n / 64 + 1]; 而不是。这是你的例子中的一个问题，因为 n = 30所以创建的数组长度为 0.
• ifnotPrime(n) 只对奇数值返回有效结果。将这个函数改名为 isOddPrime().

关于你的问题。

"什么是... (prime[x/64] & (1 << ((x >> 1) & 31)) 具体来说 (1 << ((x >> 1) & 31))?

x 先除以2（向右移位一个位置），因为数组中只有奇数才有位，然后将结果用31遮挡，以保留5个低阶位作为字中的位数。对于任何无符号值 x, x & 31 相当于 x % 32. x / 64 是测试该位的字号。

如上所述。1 是一个 int 因此不应左移31位。使用 1UL 确保该类型至少有32位，并且可以移位31位。

在 prime[x/64] 为什么要除以 64 而不与 32，当我们处理32位整数?

数组中的位对应奇数，所以一个32位的字包含了64个数的首要信息。32个已知是复合数的偶数和32个奇数 如果是复合数，则对应的位就会被设置。

是 int prime[n/64] 对不对 n < 64?

不是的，它是不正确的，如果。n 不成正比 64：尺寸表达式应是 (n + 63) / 64或者更好 int prime[n/64 + 1]

---

这里是一个修改后的版本，你可以传递一个命令行参数。

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

bool isOddPrime(const uint32_t prime[], unsigned x) {
    // checking whether the value of element
    // is set or not. Using prime[x/64], we find
    // the slot in prime array. To find the bit
    // number, we divide x by 2 and take its mod
    // with 32.
    return 1 ^ ((prime[x / 64] >> ((x >> 1) & 31)) & 1);
}

// Marks x composite in prime[]
void makeComposite(uint32_t prime[], unsigned x) {
    // Set a bit corresponding to given element.
    // Using prime[x/64], we find the slot in prime
    // array. To find the bit number, we divide x
    // by 2 and take its mod with 32.
    prime[x / 64] |= (1UL << ((x >> 1) & 31));
}

// Prints all prime numbers smaller than n.
void bitWiseSieve(unsigned n) {
    // Assuming that n takes 32 bits, we reduce
    // size to n/64 from n/2.
    uint32_t prime[n / 64 + 1];

    // Initializing values to 0 .
    memset(prime, 0, sizeof(prime));

    // 2 is the only even prime so we can ignore that
    // loop starts from 3 as we have used in sieve of
    // Eratosthenes .
    for (unsigned i = 3; i * i <= n; i += 2) {
        // If i is prime, mark all its multiples as composite
        if (isOddPrime(prime, i)) {
            for (unsigned j = i * i, k = i << 1; j < n; j += k)
                makeComposite(prime, j);
        }
    }

    // writing 2 separately
    if (n >= 2)
        printf("2\n");

    // Printing other primes
    for (unsigned i = 3; i <= n; i += 2) {
        if (isOddPrime(prime, i))
            printf("%u\n", i);
    }
}

// Driver code
int main(int argc, char *argv[]) {
    unsigned n = argc > 1 ? strtol(argv[1], NULL, 0) : 1000;
    bitWiseSieve(n);
    return 0;
}

Answer 2

1)x%32 相当于 x&31基本上是一个逻辑性的、最不重要的5位。((x>>1)&31) 意味着 ((x/2)%32)和 1<<x 途径 2^x 所以你的问题是 2^((x/2)%32).

2)在实现上的一个优化是，它完全跳过了所有的偶数。

3)n 能少于64