DPST1092 Revision 06 Questions

Revision Exercise: Set nth Bit

Download set_bit.c, or copy it to your CSE account using the following command:

cp -n /import/reed/A/dp1092/public_html/26T2/activities/set_bit/files.cp/set_bit.c set_bit.c

Your task is to add code to this function in set_bit.c:

INTERNAL ERROR MISSING FILE: "./activities/set_bit/activities/set_bit/files.cp/set_bit.c"

Add code to the function set_bit_position so that, given an integer position and a uint32_t value, you returns the value with the bit at indicated by position set to 1.

For example:

./set_bit 0 0
1
./set_bit 2 0
4                           # note: 4 == 0b100 
./set_bit 2 4
4
./set_bit 0 4294967295
4294967295

When you think your program is working you can use autotest to run some simple automated tests:

1092 autotest set_bit

Revision Exercise: Get the first n bits of a number

Download first_n_bits.c, or copy it to your CSE account using the following command:

cp -n /import/reed/A/dp1092/public_html/26T2/activities/first_n_bits/files.cp/first_n_bits.c first_n_bits.c

Your task is to add code to this function in first_n_bits.c:

INTERNAL ERROR MISSING FILE: "./activities/first_n_bits/activities/first_n_bits/files.cp/first_n_bits.c"

Add code to the function first_n_bits so that, given an integer n and a uint32_t type value, it returns only the first n bits of the value.

For example:

./first_n_bits 3 8                # note: 8 == 0b1000 
0
./first_n_bits 2 15                # note: 15 == 0b1111 
3                                    # note: 3 == 0b11 
./first_n_bits 4 251               # note: 251 == 0b11111011 
11                                   # note: 11 == 0b1011 
./first_n_bits 16 4294967295
65535

You might want to use a mask to get only the first n bits of a number. For example, if we wanted the first 2 bits of the number 14, i.e. n = 2 and value = 14 = 0b00001110.
To get the first two bits, we need a mask with 1 only in the bit positions we want to save, in this case mask = 0b0011 = 0x3.
To get the first two bits only, we would use value & mask

value 0000 1110 &
mask  0000 0011
=     0000 0010

Think about how to create a mask with n 1s at the beginning. You could consider cases like 16 - 1 = 15, or in binary 0b10000 - 0b1 = 0b1111. Does this pattern hold for larger powers of two?

When you think your program is working you can use autotest to run some simple automated tests:

1092 autotest first_n_bits

Revision Exercise: Toggle bits of a number

Download bitwise_toggle.c, or copy it to your CSE account using the following command:

cp -n /import/reed/A/dp1092/public_html/26T2/activities/bitwise_toggle/files.cp/bitwise_toggle.c bitwise_toggle.c

Your task is to add code to this function in bitwise_toggle.c:

INTERNAL ERROR MISSING FILE: "./activities/bitwise_toggle/activities/bitwise_toggle/files.cp/bitwise_toggle.c"

Add code to the function flip_bits so that, given value as a uint32_t, the bit in value corresponding to each position in the position array is flipped and this new value is returned.

The 0th position corresponds to the rightmost bit, the 31st position corresponds to the leftmost bit. If a position occurs more than once in positions, the bit should only be flipped once. If a position is less than 0 or greater than 31 then it should be ignored.

./bitwise_toggle 0 0
1
./bitwise_toggle 1 0
0
./bitwise_toggle 5 0 2           # note: 5 == 0b101
0
./bitwise_toggle 109 0 7 0       # note: 109 == 0b01101101
236                                 # note: 236 == 0b11101100

The XOR (^) operator might be helpful for this exercise.

When you think your program is working you can use autotest to run some simple automated tests:

1092 autotest bitwise_toggle

Revision Exercise: Get a specific byte from a number

Download get_nth_byte.c, or copy it to your CSE account using the following command:

cp -n /import/reed/A/dp1092/public_html/26T2/activities/get_nth_byte/files.cp/get_nth_byte.c get_nth_byte.c

Your task is to add code to this function in get_nth_byte.c:

INTERNAL ERROR MISSING FILE: "./activities/get_nth_byte/activities/get_nth_byte/files.cp/get_nth_byte.c"

Add code to the function get_nth_byte so that, given a (uint32_t) number and an integer n, you return the nth byte in number
If the n is invalid (n is greater than 3 or less than 0), you should print an error.
For example:

./get_nth_byte 1 3
Byte 3 of 1 (0x00000001) is 0 (0x00)
./get_nth_byte 0xdeadbeef 0
Byte 0 of -559038737 (0xdeadbeef) is 239 (0xef)
./get_nth_byte 0xdeadbeef 1
Byte 1 of -559038737 (0xdeadbeef) is 190 (0xbe)
./get_nth_byte 0xdeadbeef 2
Byte 2 of -559038737 (0xdeadbeef) is 173 (0xad)
./get_nth_byte 0xdeadbeef 3
Byte 3 of -559038737 (0xdeadbeef) is 222 (0xde)
./get_nth_byte 0xdeadbeef 4
Error: n = 4 is not a valid byte index.

When you think your program is working you can use autotest to run some simple automated tests:

1092 autotest get_nth_byte

Revision Exercise: Sum of bytes in a Number

Download byte_sum.c, or copy it to your CSE account using the following command:

cp -n /import/reed/A/dp1092/public_html/26T2/activities/byte_sum/files.cp/byte_sum.c byte_sum.c

Your task is to add code to this function in byte_sum.c:

INTERNAL ERROR MISSING FILE: "./activities/byte_sum/activities/byte_sum/files.cp/byte_sum.c"

Add code to the function byte_sum so that, given a (uint32_t) number you return the sum of all 4 bytes in the number.
For example:

./byte_sum 1
1
./byte_sum 0x01020304
10
./byte_sum 255        # note: 255 == 0x000000FF
255
./byte_sum 256        # note: 256 == 0x00000100
1
./byte_sum 1500
225

When you think your program is working you can use autotest to run some simple automated tests:

1092 autotest byte_sum

Revision Exercise: Find Binary Gaps

Download binary_gaps.c, or copy it to your CSE account using the following command:

cp -n /import/reed/A/dp1092/public_html/26T2/activities/binary_gaps/files.cp/binary_gaps.c binary_gaps.c

Your task is to add code to this function in binary_gaps.c:

INTERNAL ERROR MISSING FILE: "./activities/binary_gaps/activities/binary_gaps/files.cp/binary_gaps.c"

Add code to the function count_binary_gaps so that, given a uint32_t value, it returns the number of binary gaps.

A binary gap is a sequence of one or more 0s surrounded on both sides by 1s in the binary representation of the value. You should ignore leading and trailing 0s.

For example:

./binary_gaps 529        # note: 529 == 0b1000010001 
2
./binary_gaps 20         # note: 20 == 0b10100 
1

When you think your program is working you can use autotest to run some simple automated tests:

1092 autotest binary_gaps

Revision Exercise: Hamming Distance

Download hamming_distance.c, or copy it to your CSE account using the following command:

cp -n /import/reed/A/dp1092/public_html/26T2/activities/hamming_distance/files.cp/hamming_distance.c hamming_distance.c

Your task is to add code to this function in hamming_distance.c:

INTERNAL ERROR MISSING FILE: "./activities/hamming_distance/activities/hamming_distance/files.cp/hamming_distance.c"

The Hamming Distance between two numbers is the number of positions where the bits are different. It's often used in telecommunications to detect and correct bit errors when transmitting digital signals.

Add code to the function hamming_distance so that, given two unsigned 32-bit integers, you calculate how many bits they differ by. For example:

./hamming_distance 9 4
3
./hamming_distance 100 100
0
./hamming_distance 0 0xFFFFFFFF
32

Consider the first example, the hamming distance between 9 == 0b00001001 and 4 = 0b00000100. Lets compare them one bit at a time.

bit index  | 7| 6| 5| 4| 3| 2| 1| 0|
-----------|--|--|--|--|--|--|--|--|
9 (dec) == | 0| 0| 0| 0| 1| 0| 0| 1|
-----------|--|--|--|--|--|--|--|--|
4 (dec) == | 0| 0| 0| 0| 0| 1| 0| 0|

We can see from here that the bits differ in three places (the 0th, 2nd and 3rd bits), so the hamming distance is three.

When you think your program is working you can use autotest to run some simple automated tests:

1092 autotest hamming_distance