DPST1092 Revision 06 Sample Solutions

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

Sample solution for set_bit.c

// Sample solution for COMP1521 exercises
//
// Set bit at a position n
//
// Author: Jimmy Kirkpatrick <z5480564@unsw.edu.au>

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

uint32_t set_bit_position(int position, uint32_t value);

int main(int argc, char *argv[]) {
    if (argc != 3) {
        fprintf(stderr, "Usage: %s <position> <value>\n", argv[0]);
        return 1;
    }
    int position = atoi(argv[1]);
    uint32_t value = atoi(argv[2]);
    printf("%u\n", set_bit_position(position, value));
    return 0;
}

// given a position and a value,
// returns the value with the bit at the position set to 1
uint32_t set_bit_position(int position, uint32_t value) {
    return value | (1U << position);
}

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

Sample solution for first_n_bits.c

// Sample solution for COMP1521 exercises
//
// Extracts first n bits of a number
//
// Author: Jimmy Kirkpatrick <z5480564@unsw.edu.au>

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#define N_BITS 32

uint32_t first_n_bits(int n, uint32_t value);

int main(int argc, char *argv[]) {
    if (argc != 3) {
        fprintf(stderr, "Usage: %s <n> <value>\n", argv[0]);
        return 1;
    }
    int n = atoi(argv[1]);
    uint32_t value = atoi(argv[2]);
    printf("%u\n", first_n_bits(n, value));
    return 0;
}

// given an integer n and a uint32_t value
// returns the first n bits of the value
uint32_t first_n_bits(int n, uint32_t value) {
    if (n >= N_BITS) return value; // important edge case
    return value & ((1U << n) - 1); // mask of size n, for n <= 31
}

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

Sample solution for bitwise_toggle.c

// Flips bits specified in positions array from a value

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

uint32_t flip_bits(int *positions, int length, uint32_t value);

int main(int argc, char *argv[]) {
    if (argc < 2) {
        fprintf(stderr, "Usage: %s <value> [positions]\n", argv[0]);
        return 1;
    }

    int length = argc - 2;
    int *positions = malloc(length * sizeof(int));

    for (int i = 0; i < length; i++) {
        positions[i] = atoi(argv[i + 2]);
    }

    uint32_t value = atoi(argv[1]);
    printf("%u\n", flip_bits(positions, length, value));

    free(positions);
    return 0;
}

// flips bits in value at positions specified in positions array
uint32_t flip_bits(int *positions, int length, uint32_t value) {
    uint32_t used_positions = 0;
    for (int i = 0; i < length; i++) {
        int pos = positions[i];
        if (pos >= 0 && pos < 32) {
            if ((used_positions & (1U << pos)) == 0) {
                value ^= (1U << pos);
                used_positions |= (1U << pos);
            }
        }
    }
    return value;
}

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

Sample solution for get_nth_byte.c

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

#define BYTE_LEN    8
#define NUM_BYTES   4
#define BYTE_MASK   0xFF

uint32_t get_nth_byte(uint32_t number, int n);

int main(int argc, char *argv[]) {
    if (argc != 3) {
        printf("Usage: %s number byte_index\n", argv[0]);
    }

    uint32_t number = strtol(argv[1], NULL, 0);
    int byte_index = strtol(argv[2], NULL, 0);
    uint32_t byte = get_nth_byte(number, byte_index);

    printf("Byte %d of %d (0x%08x) is %d (0x%02x)\n", byte_index, number, number, byte, byte);
}

uint32_t get_nth_byte(uint32_t number, int n) {
    if (n < 0 || n >= 4) {
        printf("Error: n = %d is not a valid byte index.\n", n);
        exit(1);
    }

    return (number >> n*8) & BYTE_MASK;
}

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

Sample solution for byte_sum.c

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

#define BYTE_LEN    8
#define NUM_BYTES   4
#define BYTE_MASK   0xFF

int byte_sum(uint32_t number);

int main(int argc, char *argv[]) {
    if (argc != 2) {
        printf("Usage: %s number\n", argv[0]);
    }

    uint32_t number = strtol(argv[1], NULL, 0);
    printf("%d\n", byte_sum(number));
}

int byte_sum(uint32_t number) {
    int sum = 0;
    for (int i = 0; i < NUM_BYTES; i++) {
        sum += (number >> (i * BYTE_LEN)) & BYTE_MASK;

    }
    return 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

Sample solution for binary_gaps.c

// Counts the number of binary gaps in a 32-bit integer

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#define TRUE    1
#define FALSE   0

int count_binary_gaps(uint32_t value);

int main(int argc, char *argv[]) {
    if (argc != 2) {
        fprintf(stderr, "Usage: %s <value>\n", argv[0]);
        return 1;
    }

    uint32_t value = (uint32_t)atoi(argv[1]);
    int gaps = count_binary_gaps(value);
    printf("%d\n", gaps);

    return 0;
}

// given a uint32_t value, returns the number of binary gaps
int count_binary_gaps(uint32_t value) {
    int num_gaps = 0;
    int in_gap = 0;
    int prev_bit = 0;

    for (int i = 31; i >= 0; i--) {
    // get individual bit

        int bit = (value >> i) & 1;

        if (bit == 0) {
            if (prev_bit == 1) {
                in_gap = TRUE;
            }
        }

        if (bit == 1) {
            if (in_gap == TRUE) {
                num_gaps++;
                in_gap = FALSE;
            }
        }
        prev_bit = bit;
    }
    return num_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

Sample solution for hamming_distance.c

// Calculates the Hamming Distance between two numbers

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

int hamming_distance(uint32_t a, uint32_t b);

int main(int argc, char *argv[]) {
    if (argc != 3) {
        fprintf(stderr, "Usage: %s <number1> <number2>\n", argv[0]);
        return 1;
    }

    uint32_t num1 = strtol(argv[1], NULL, 0);
    uint32_t num2 = strtol(argv[2], NULL, 0);

    printf("%d\n", hamming_distance(num1, num2));

    return 0;
}

// given two numbers, calculate the number of bits they differ by
int hamming_distance(uint32_t a, uint32_t b) {
    int distance = 0;
    uint32_t xor = a ^ b;

    while (xor != 0) {
        distance += (xor & 1);
        xor >>= 1;
    }

    return distance;
}