Sieve of Eratosthenes using a bit array

0
votes

I have a bit array prime[]of unsigned int. I wish to implement a Sieve of Eratosthenes using this array, by having each bit represent a number n. That is, given n, the array element that holds the bit that corresponds to n would be prime[n/32] and the specific bit would be in position n%32.

My testBitIs0(int n) function returns 1 when the number is prime (if its bit == 0), otherwise 0: 

return ( (prime[n/32] & (1 << (n%32) )) != 0);

My setBit(int n) function simply sets the bit to 1 at the corresponding position: 

int i = n/32;
int pos = n%32;
unsigned int flag = 1;
flag = flag << pos;
prime[i] = prime[i] | flag;

The issue that I'm having is that when I call setBit with multiples of a prime number, I don't think it sets the bit correctly. When I call setBit with multiples of a prime number (such as 4, 6, 8, etc. for the number 2) the next time I run this line: 

if(testBitIs0(i)) { ... }

With i = 4/6/8/etc it will still return 1 when it should return 0.
Can someone please check my code to make sure I am implementing this correctly? Thanks.

1
csieve-of-eratosthenesbitarray
Why does testBitIs0 check if the bit is not zero? – interjay
Please post a complete example... – Lindydancer
Hang on, you said testBitIs0 returns 1 when the number is prime (if its bit == 0), but in the implementation you compare against false instead of true. You can just have testBitIs0 be return !(prime[n/32] & (1 << (n%32))). – Vicky

1 Answers

0
votes

This looks like it does what you're after. There's a bit array and some bit twiddling functions too.

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