Flipping Bit Errors

Question

The caller wants us to answer the following 64 questions:

is base prime? is base + 1 prime? is base + 2 prime? is base + 3 prime? ... is base + 63 prime?

The function is supposed to build and return a 64-bit unsigned long long where each bit holds the answer to the corresponding question: bit #k of the return value tells whether base + k is a prime number.

Not sure where I went wrong here. The function should output 0x820A00A08800228AULL but I'm getting the 10004514. I thought to start with the MSB and shift left would build it bit by bit.

int prime( unsigned long long n ){
    int a;

    for( a = 2; a<=sqrt((double)n); a++ ){
        if( n%a == 0 )
            return 0;
    }
    if( a == n )
        return 1;
}

unsigned long long setPrimeBits( unsigned long long base ){
    int a;
    unsigned long long b = 0x000000000000000ULL;

    for( a=63; a>=0; a-- ){
        if( prime( base+a ) ){
            b |= 1;
            b = b<<1;
        }//end if
        else b = b<<1;
    }//end for
    return b;
}

Main & output as follows...

int main(){
    printf( "%16X\n", setPrimeBits( 100 ));
}
        10004514

Answer 1

1. Your prime() function exhibits undefined behavior. If it doesn't find a prime, the final conditional will also be false (because a is near the sqrt(n), not near n), which means you will have no executed return statement. To fix this, Just return 1 if you complete the for loop (that is, you find no prime divisors).

2. You want to print an unsigned long long. The format string for that is %016llX.

3. You shift b one too many times. Let's assume the last loop of the for loop (computing a + 0) is prime. You'll write that to the bottom bit, and then move it over one place.

Fixing these errors, we get some code that looks like:

#include <stdio.h>
#include <math.h>

int prime( unsigned long long n ){
    int a;

    for(a = 2; a<=sqrt((double)n); a++)
        if( n%a == 0 )
            return 0;

    return 1;
}

unsigned long long setPrimeBits( unsigned long long base ){
    int a;
    unsigned long long b = 0x000000000000000ULL;

    for(a = 63; a >= 0; a--) {
        b = b << 1;
        if(prime(base+a))
            b |= 1;
    }

    return b;
}

int main(){
    printf( "%16llX\n", setPrimeBits( 100 ));
}

Which, when run, reports:

[12:54pm][wlynch@watermelon /tmp] ./pr 
820A00A08800228A

And, because there seems to be confusion about the left-shifting in other answers, you could write an equivalent setPrimeBits() that looks like this:

unsigned long long setPrimeBits( unsigned long long base ){
    int a;
    unsigned long long b = 0x000000000000000ULL;

    for(a = 0; a < 64; a++)
        if (prime(base+a))
            b |= (1ULL << a);           

    return b;
}