У меня есть битовый массив prime[]
of unsigned int
. Я хочу реализовать решето Эратосфена, используя этот массив, чтобы каждый бит представлял число n
. То есть, учитывая n
, элемент массива, который содержит бит, соответствующий n
, будет prime[n/32]
, а конкретный бит будет в позиции n%32
.
Моя функция testBitIs0(int n)
возвращает 1, когда число простое (если его бит == 0), иначе 0:
return ( (prime[n/32] & (1 << (n%32) )) != 0);
Моя функция setBit(int n)
просто устанавливает бит в 1 в соответствующей позиции:
int i = n/32;
int pos = n%32;
unsigned int flag = 1;
flag = flag << pos;
prime[i] = prime[i] | flag;
Проблема, с которой я сталкиваюсь, заключается в том, что когда я вызываю setBit
с кратным простому числу, я не думаю, что он устанавливает бит правильно. Когда я вызываю setBit
с кратным простому числу (например, 4, 6, 8 и т. д. для числа 2), в следующий раз, когда я запускаю эту строку:
if(testBitIs0(i)) { ... }
С i = 4/6/8/etc
он по-прежнему будет возвращать 1, когда должен возвращать 0.
Может ли кто-нибудь проверить мой код, чтобы убедиться, что я правильно его реализую? Спасибо.
testBitIs0
проверяет, равен ли бит не нулю? - person interjay   schedule 18.04.2013testBitIs0
возвращает 1, когда число простое (если его бит == 0), но в реализации вы сравниваете с ложным, а не с истинным. Вы можете простоtestBitIs0
бытьreturn !(prime[n/32] & (1 << (n%32)))
. - person Vicky   schedule 18.04.2013