Как я могу решить побитовый Seive с использованием 64-битных вместо 32-битных?В чем разница между этими двумя?

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 бита, int.Во-первых, он, вероятно, должен unsigned, поскольку вы можете иметь 1 << 63 (и, как сказал Натан Оливер 1LLU <<).

31 равно 0x1F, поэтому вы заставляете сдвиг быть меньше 31, поэтомучто с этим сдвигом нет проблем (в 32-битной версии все еще проблема с неподписанным IMHO).

Две операции, которые вы задаете после, являются совершенно разными операциями.Сдвиг j>>1 делается для удаления четных чисел, так как мы знаем, что это никогда не простые числа (см. j+=2*i).

Итак, две вещи здесь:

• (j>>1)&31 убирает поддержку четных чисел, так как при увеличении на 2*i
• status[j>>6] выбирается соответствующий элемент в массиве для j.Но выбранное здесь значение неверно, так как в длинном длинном целом есть 8 байтов, а не 6. Также из-за предыдущего смещения я бы предположил, что вместо этого возможно значение 9.

редактировать: неправильное утверждение о status[j>>6]