For this assignment, you are to write a C program that compiles and runs without errors or warnings. This program has several little bit-manipulation functions in it. The function prototypes should match the ones I give here. Your main function should call each of your otherfunctions. The purpose of your main function is to convince you that your other functions are working properly.

You may assume that your program is running in an environment that has 32-bit unsigneds and 64-bit unsignedlong longs, as the MS VS environment does. When we speak of the position of a bit, we follow the convention that the position of the lowest-order bit isposition 0. The rightmost bit of an unsigned is bit #0, and the leftmost bit of an unsigned is bit #31. When wesay bit field (12, 7], we mean the collection of the following 5 bits: bit #7, bit #8, bit #9, bit #10, and bit #11(not bit #12). The number on the right (next to the bracket) is the position of the lowest-order bit in the bit field,while the number on the left (next to the parenthesis) is the position of the first bit past the bit field. Bit field(5, 5] contains no bits. Bit field (6, 5] contains one bit (namely, bit #5). Bit field (32, 0] contains all 32 bits,starting with bit #0 and ending with bit #31.

As always, you are free to have your functions call other functions. On this assignment, you can save yourself significant time by doing this. Its smart to read through the assignment and see where you want to have your functions delegate some of their work to other functions.

0. unsigned highBitPosition( unsigned n );

Returns the position of the highest-order 1-bit in n. For example, if main says

highBitPosition( 0x0BABE000U )

then the function returns 27. If there are no 1-bits, then the function should return UINT_MAX.

1. unsigned highBitPosition64( unsigned long long nn );

64-bit version.

For example, if main says

highBitPosition64( 0xBABE000000000000ULL )

then the function returns 63.

For example,highBitPosition64( 0x00000000BABE0000ULL ) returns 31. If there are no 1-bits, then the

function should return UINT_MAX.

2. unsigned highBitValue( unsigned n );

Returns the place value (contribution) of the highest-order 1-bit in n. For example,

highBitValue( 0x000ABC00U )

returns 524288, which is 2 to the 19th power. If there are no 1-bits, then the function should return 0.

3. unsigned long long highBitValue64( unsigned long long nn );

64-bit version. For example,

highBitValue64( 0x0600000000000000ULL )

returns 288230376151711744, which is 2 to the 58th power. If there are no 1-bits, then the function

should return 0.

4. int prime( unsigned long long nn );

This isnt actually a bit-manipulation function, but its part of the job that the next function needs to do.primes job is to return whether nn is a prime number (so it always returns 0 or 1). As you probably recall from math, a prime number is a number greater than 1 with no positivefactors except 1 and itself. The first 4 prime numbers are 2, 3, 5, and 7. If youve writtena function to test for primality before, you probably dont need any more direction. If not,though, heres a pretty good, pretty simple, algorithm that tests a number nn for

primality:

if nn is less than 4, then its prime iff (if and only if) its greater than 1.

otherwise, if nn is even, then its not prime

otherwise, loop through trial factors 3, 5, 7, 9, ....:

if nn is divisible by the trial factor, return 0 (n isnt prime, its divisible by the trial factor)

if nn divided by the trial factor is >= the trial factor, return 1 (nn is prime, we checked all

necessary trial factors without finding an actual factor)

For example, if we were checking nn = 121 for primality, our loop would proceed as follows, where tf is

the trial factor, nn%tf tells us whether nn is divisible by tf, and nn/tf tells us whether

weve checked enough values of tf:

tf	nn%tf	nn/tf
3	1	40
5	1	24
7	2	17
9	4	13
11	0

(At this point, since nn%tf is 0, we return 0. 121 is not prime.)

For another example, if we were checking nn = 29 for primality, our loop would proceed as follows:

tf	nn%tf	nn/tf
3	2	9
5	4	5

tf nn%tf nn/tf3 2 95 4 5 (At this point, since tf >= nn/tf, we return 1. 29 is prime)

Remember that nn is an unsigned long long. If you make your trial factor an unsigned, you have to thinkcarefully about the possibility of the trial factor overflowing. But if you make your trial

factor an unsigned long long, then overflow shouldnt be a concern.

To test your prime function for small values, you can write a little loop to find the average of all primenumbers in the range [0,100]. The correct answer is 42.400000. (The answer is a bit lessthan 50 because there are a few more primes among the smaller numbers than among the larger numbers.)

To test your prime function for large values, you can write a little loop to find the largest 64-bit primenumber. (Start at the largest 64-bit number, ULLONG_MAX, and decrement the numberuntil its prime.) The correct answer is ULLONG_MAX - 58, which is 2⁶⁴59 .

5. unsigned long long setPrimeBits( unsigned long long base );

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.

For instance, if the caller

sayssetPrimeBits( 100 )

then the function should return 0x820A00A08800228AULL. The highest-order bit is a 1, saying that 100+63 == 163 is prime.

The lowest-order bit is 0, saying that 100+0 == 100 is not prime

Lets say that if adding the base to any of the numbers [0,63] overflows, well just perform the primality test on the resulting 64-bit sum. (That way we dont need to worry about overflow.)

Of course, youll write this function so that it calls the last function: you wont repeat the work you did in the last function to figure out whether a number is prime.

This sort of computation can be useful. Were storing the answers to 64 different questions in a single variable, which can be a lot more efficient to store and to transmit than storing them in 64 different variables.

6. unsigned reverse( unsigned n );

The function returns the result of reversing the order of bits in n. For instance, if ns bits were

00010011 01010111 10011011 11011111

then the value returned would have bits

11111011 11011001 11101010 11001000

7. unsigned long long reverse64( unsigned long long nn );

64-bit version

8. int threeInARow( unsigned n );

Return whether n has 3 1-bits in a row.

For example, if n's bits were

11010110 00110110 10110100 00101011

the function would return 0 (no).

For another example, if n's bits were

11010110 00110111 10110100 00111011

the function would return 1 (yes).

9. int final( unsigned a, unsigned b );

This trickily super-simple function returns 0 or 1. If a and b are identical, the function returns 0.

Otherwise, the function returns the most significant bit of b that is different from the corresponding bit in a.

For example, suppose that the bits of a are

00101001 01110101 11011101 01011011

and that the bits of b are

00101001 01111011 00001111 11110000

The most significant bit of b that differs from a is bit #19 (underlined). Since bit #19 of b is 1, thefunction returns 1. If bs bit #19 were turned off, then the function would return 0, because bs bit #18 is 0 (and is different from as bit #18).

Here are the 10 prototypes, so you can just copy & paste them into your program:

unsigned highBitPosition( unsigned n );

unsigned highBitPosition64( unsigned long long n );

unsigned highBitValue( unsigned n );

unsigned long long highBitValue64( unsigned long long n );

int prime( unsigned long long n );

unsigned long long setPrimeBits( unsigned long long base );

unsigned reverse( unsigned n );

unsigned long long reverse64( unsigned long long n );

int threeInARow( unsigned n );

int final( unsigned a, unsigned b );