c++ - Sieve of eratosthenes : bit wise optimized -

after searching net came know bit-wise version of sieve of eratosthenes pretty efficient. problem unable understand math/method using.

the version have been busy looks 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 understood (please correct me if wrong):

1. statement in line 1 checks if number composite.
2. statement in line 2 marks number 'n' composite.
3. the program storing value 0 or 1 @ bit of int. tends reduce memory usage x/32. (x size have been used had int been used store 0 or 1 instead of bit in solution above)

points going above head of :

1. how finction in line 1 functioning.how function making sure number composite or not.
2. how function in line 2 setting bit.
3. i came know bitwise sieve timewise efficient well. because of use of bitwise operators or else contributing well.

any ideas or suggestions?

technically, there bug in code well:

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

divides max 64, if max not exact multiple of 64, array 1 element short.

line 1: let's pick apart:

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

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

since "odd" numbers possible primes, divide n two: (n>>1).

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

finally, use & combine value on left value on right.

so, result true if element n has bit number n modulo 32 set.

the second line same concept, uses |= (or equal) set bit corresponding multiple.