Sieve of eratosthenes : bit wise optimized

问题:

After searching the net I came to know that the bit-wise version of the sieve of eratosthenes is pretty efficient. The problem is I am unable to understand the math/method it is using.

The version that I have been busy with looks like this:

#define MAX 100000000
#define LIM 10000

unsigned flag[MAX>>6]={0};

#define ifc(n) (flag[n>>6]&(1<<((n>>1)&31)))         //LINE 1
#define isc(n) (flag[n>>6]|=(1<<((n>>1)&31)))        //LINE 2

void sieve() {
    unsigned i, j, k;
    for(i=3; i<LIM; i+=2)
        if(!ifc(i))
            for(j=i*i, k=i<<1; j<LIM*LIM; j+=k)
                isc(j);
}

Points that I understood (Please correct me if I am wrong):

1. Statement in line 1 checks if the number is composite.
2. Statement in line 2 marks the number 'n' as composite.
3. The program is storing the value 0 or 1 at a bit of an int. This tends to reduce the memory usage to x/32. (x is the size that would have been used had an int been used to store the 0 or 1 instead of a bit like in my solution above)

Points that are going above my head as of now :

1. How is the finction in LINE 1 functioning.How is the function making sure that the number is composite or not.
2. How is function in LINE 2 setting the bit.
3. I also came to know that the bitwise sieve is timewise efficient as well. Is it because of the use of bitwise operators only or something else is contributing to it as well.

Any ideas or suggestions?

回答1:

Technically, there is a bug in the code as well:

unsigned flag[MAX>>6]={0};

divides MAX by 64, but if MAX is not an exact multiple of 64, the array is one element short.

Line 1: Let's pick it apart:

 (flag[n>>6]&(1<<((n>>1)&31)))

The flag[n>>6] (n >> 6 = n / 64) gives the 32-bit integer that holds the bit value for n / 2.

Since only "Odd" numbers are possible primes, divide n by two: (n>>1).

The 1<<((n>>1)&31) gives us the bit corresponding to n/2 within the 0..31 - (& 31 makes sure that it's "in range").

Finally, use & to combine the value on the left with the value on the right.

So, the result is true if element for n has bit number n modulo 32 set.

The second line is essentially the same concept, just that it uses |= (or equal) to set the bit corresponding to the multiple.