Project Euler Problem 10 - Efficient Algorithm

I attempted Project Euler's problem 10 using the very easy algorithm and the running time looks like hours. So I googled for an efficient algorithm and found this by Shlomif Fish. The code is reproduced below:

int main(int argc, char * argv[])
{
    int p, i;
    int mark_limit;
    long long sum = 0;

    memset(bitmask, '\0', sizeof(bitmask));
    mark_limit = (int)sqrt(limit);

    for (p=2 ; p <= mark_limit ; p++)
    {
        if (! ( bitmask[p>>3]&(1 << (p&(8-1))) ) )
        {
            /* It is a prime. */
            sum += p;
            for (i=p*p;i<=limit;i+=p)
            {
                bitmask[i>>3] |= (1 << (i&(8-1)));
            }
        }
    }
    for (; p <= limit; p++)
    {
        if (! ( bitmask[p>>3]&(1 << (p&(8-1))) ) )
        {
            sum += p;
        }
    }开发者_如何学运维

I have problems understanding the code. Specifically, how does this bit shifting code able to determine whether a number is prime or not.

   if (! ( bitmask[p>>3]&(1 << (p&(8-1))) ) )
        {
            /* It is a prime. */
            sum += p;
            for (i=p*p;i<=limit;i+=p)
            {
                bitmask[i>>3] |= (1 << (i&(8-1)));
            }
        }

Can someone please explain this code block to me, especially this part ( bitmask[p>>3]&(1 << (p&(8-1)? Thank you very much.

The code is a modified Sieve of Eratosthenes. He is packing one number into one bit: 0 = prime, 1 = composite. The bit shifting is to get to the correct bit in the byte array.

 bitmask[p>>3]

is equivalent to

 bitmask[p / 8]

which selects the correct byte in the bitmask[] array.

(p&(8-1))

equals p & 7, which selects the lower 3 bits of p. This is equivalent to p % 8

Overall we are selecting bit (p % 8) of byte bitmask[p / 8]. That is we are selecting the bit in the bitmask[] array which represents the number p.

The 1 << (p % 8) sets up a 1 bit correctly located in a byte. This is then AND'ed with the bitmask[p / 8] byte to see if that particular bit is set or not, thus checking whether p is a prime number.

The overall statement equates to if (isPrime(p)), using the already completed part of the sieve to help extend the sieve.

The bitmask is acting as an array of bits. Since you can't address bits individually, you first have to access the byte and then modify a bit within it. Shifting right by 3 is the same as dividing by 8, which puts you on the right byte. The one is then shifted into place by the remainder.

x>>3 is equivalent to x/8

x&(8-1) is equivalent to x%8

But on some older systems, the bit manipulations may have been faster.

The line sets the ith bit, where i has been determined not to be prime because it is a multiple of another prime number number:

bitmask[i>>3] |= (1 << (i&(8-1)));

This line checks that the pth bit is not set, which means it is prime, since if it wasn't prime it would have been set by the line above.

if (! ( bitmask[p>>3]&(1 << (p&(8-1))) ) )