Решето Эратосфена с использованием битового массива

У меня есть битовый массив 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.
Может ли кто-нибудь проверить мой код, чтобы убедиться, что я правильно его реализую? Спасибо.


person yiwei    schedule 18.04.2013    source источник
comment
Почему testBitIs0 проверяет, равен ли бит не нулю?   -  person interjay    schedule 18.04.2013
comment
Пожалуйста, опубликуйте полный пример...   -  person Lindydancer    schedule 18.04.2013
comment
Подождите, вы сказали, что testBitIs0 возвращает 1, когда число простое (если его бит == 0), но в реализации вы сравниваете с ложным, а не с истинным. Вы можете просто testBitIs0 быть return !(prime[n/32] & (1 << (n%32))).   -  person Vicky    schedule 18.04.2013


Ответы (1)


Похоже, он делает то, что вам нужно. Есть битовый массив и некоторые функции битового вращения.

http://bcu.copsewood.net/dsalg/bitwise/bitwise.html

person Chris Lawson    schedule 18.04.2013