c++ - 如何使用 64 位而不是 32 位解决按位 seive？这两者有什么区别？

Question

#define SZ 100000010
long long int status[SZ/64+1];
bool check( long long int N, long long int pos)
{
    return (bool)(N & (1<<pos));
}
long long int Set( long long int N, long long int pos)
{
    return N=N | (1<<pos);
}
void bitwise_seive()
{
    long long int cnt=1;
    for( long long int i=3; i<=sqrt(SZ); i+=2)
    {
        if(check( status[i>>6], ((i>>1)&31))==0)
        {
            for( long long int j=i*i; j<=SZ; j+=(i*2))
            {
                status[j>>6]=Set( status[j>>6], (j>>1)&31);
            }
        }
    }
}

第 20 行:

Set( status[j>>6], (j>>1)&31)

这是什么意思？

如果我这样做:

Set( status[j>>5], j&31) 

代替:

Set( status[j>>6], (j>>1)&31)

这有什么区别？

Answer 1

基本上，您的标记有 64 个整数，一个代表 64 位 long long int 中的每一位。首先，它可能应该是unsigned ，因为你可以有1 << 63 (正如 NathanOliver 所说 1LLU << )。

31 是 0x1F ，因此您强制转换小于 31，以便此转换没有问题(在 32 位版本中，未签名的恕我直言仍然存在问题)。

你后面给出的两个操作是完全不同的操作。类次j>>1这样做是为了删除偶数，因为我们知道这些从来都不是素数(参见 j+=2*i )。

这里有两件事:

• (j>>1)&31删除对偶数的支持，因为增加是 2*i
• status[j>>6]为 j 选择数组中的适当元素.但是您在此处选择的值是错误的，因为 long long int 中有 8 个字节，而不是 6 个字节。另外由于之前的偏移量，我假设该值可能是 9。

编辑:关于 status[j>>6] 的错误陈述