筛网-逐位优化问题

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]中，当我们使用32位整数时，为什么要除以64而不是除以32；
3. 如果int prime[n/64]，n < 64是否正确？

我想你们每个人都遇到了按位操作Eratosthenes筛子的优化代码。我试图绕过它，对...

Answer 1

1] x%32等效于x&31：逻辑且最低有效5位。所以基本上((x>>1)&31)表示((x/2)%32)。 1<<x表示2^x，所以您要问的是2^((x/2)%32)。

Answer 2

代码中存在多个问题：