CMSC216 HW04: Review for Exam 1

Due: 11:59pm Sun 28-Sep-2025 on Gradescope
Approximately 0.83% of total grade

CODE DISTRIBUTION: hw04-code.zip

Download the code distribution every lab
See further setup instructions below

CHANGELOG: Empty

1. Rationale
- Associated Reading / Preparation
- Grading Policy
2. Codepack
3. Two's Complement Arithmetic
4. Octal and Hexadecimal Representation of Numbers
5. Questions

1 Rationale

This HW reviews concepts from the preceding weeks of the course to prepare for an exam. Solutions to the this HW along with past HWs and Labs will be posted within a few days to aid in students as they prepare for Exam 1. You may wish to consult with TAs during lab or office hours if you are unsure of how to solve problems as the exam is likely to have similar problems.

Associated Reading / Preparation

C References: Basics of C programming including control structures, pointers/addresses, memory allocation/deallocation, bit operations
Bryant and O'Hallaron: Ch 2.1-2.3 on binary representations of integers in unsigned and two's complement signed format.

Grading Policy

Credit for this HW is earned by taking the associated HW Quiz which is linked under Gradescope. The quiz will ask similar questions as those that are present in the QUESTIONS.txt file and those that complete all answers in QUESTIONS.txt should have no trouble with the quiz.

Homework and Quizzes are open resource/open collaboration. You must submit your own work but you may freely discuss HW topics with other members of the class.

See the full policies in the course syllabus.

2 Codepack

The codepack for the HW contains the following files:

File	Description
`QUESTIONS.txt`	Questions to answer
`dog_diagram.c`	C file for Problem 1
`badmem.c`	C file for Problem 2
`best_score.c`	C file to complete for Problem 3
`scores1.txt`	Data file for Problem 3
`scores2.txt`	Data file for Problem 3
`scores3.txt`	Data file for Problem 3
`scores-empty.txt`	Data file for Problem 3

3 Two's Complement Arithmetic

Modern computers represent all data using bits, collections of 1's and 0's. Integer data pervades many applications so understanding the bit-level representation of integers lends insight into their strengths and limitations. The two's complement representation for integers is by far the most common used by hardware and is therefore considered specially in this HW. C provides facilities to manipulate data at the bit level using logical and shift operations which are also discussed.

Understanding two's complement is necessary to complete a problem QUESTIONS.txt. The short presentation below gives the basics of two's complement but you should study the material presented in our textbook and lecture to supplement it.

The principles of two's complement representation for integers are as follows.

Fix a number of bits to represent integers such as 8 bits or 32 bits
Zero is the bit string of all 0s. In 8 bits this is
```
0000 0000
```
Positive numbers always start with a 0. In 8 bits +91 would be
```
0101 1011
```
Negative numbers always start with a 1. In 8 bits, the following is a negative number
```
1010 0101
```
To determine the value of negative number in two's complement or negate it:
1. Invert the bits: ones become zeros, zeros to ones. The C operator invert is the tilde ~ symbol.
2. Add 1
This process on the above negative number is as follows.
```
  ~ 1010 0101 = negative number
  -----------
    0101 1010 = +90
  +         1
  -----------
    0101 1011 = +91
```
So the above negative number is -91 as 91 is its twos complement.
The same process works to convert from positive to negative.
```
  ~ 0101 1011 = +91
  -----------
  ~ 1010 0100 = negative number
  +         1
  -----------
  ~ 1010 0101 = -91
```
So the above negative number is -91 as 91 is its twos complement.
C's unary negation operator performs these two steps of inverting and adding 1:
```
int p = 91;  // 0101 1011
int n = -p;  // 1010 0101
```
The context for interpreting bits matters. When interpreting bits as an unsigned quantity, each bit represents a power of 2 that should be added.
```
  unsigned char p = 0b10100101;
  //   1   0    1   0   0   1   0   1
  // 128 + 0 + 32 + 0 + 0 + 4 + 0 + 1
  // = 165
```
In contrast, the same bits when interpreted in a signed context are a negative quantity. In the 2's complement representation, the highest order bit is associated with a negative power of two.
```
  char p = 0b10100101;  // signed quantity, negative due to leading 1
  //    1   0    1   0   0   1   0   1
  // -128 + 0 + 32 + 0 + 0 + 4 + 0 + 1
  // = -91
```
Due to 0 starting with a 0, there is one more bit string available for negative numbers than for positive numbers. This explains the asymmetric range of C data types. 8-bit characters have a range of -128 to +127 which are the following bit strings
```
  +127 = 0111 1111
  -128 = 1000 0000
```
Arithmetic in twos complement has some nice properties such as going from 0 to -1:
```
    0000 0000 = zero
  + 1111 1111 = -1
  -----------
    1111 1111 = -1
```
More details of arithmetic will be discussed later.

For wider bit widths than 8, extend the sign bit for numbers left as in the following

 8-bit +91: 0101 1011
16-bit +91: 0000 0000 0101 1011
 8-bit -91: 1010 0101
16-bit -91: 1111 1111 1010 0101

4 Octal and Hexadecimal Representation of Numbers

The base-10 numbering system is taught rigorously from an early age and is familiar to most students. We have seen in the earlier Two's Complement system that numbers can also written in base-2 as Binary. This is indicative of numbers being independent of any particular notation or base. Binary is frequently used in computer science but is cumbersome as it takes a LOT of digits to write a number. When bits must be written, often they are written in a base-8 Octal format or base-16 Hexadecimal format. This is in part due to their compactness: the same bits are shown with fewer printed characters. Here is a short example.

|---------+--------------+----------------+----------------+-----------------+-----------------------|
| Decimal | Byte = 8bits | Byte by 4      | Hexadecimal    | Byte by 3       | Octal                 |
|---------+--------------+----------------+----------------+-----------------+-----------------------|
|      87 |     01010111 | bin: 0101 0111 | 57 = 5*16 + 7  | bin: 01 010 111 | 127 = 1*8^2 + 2*8 + 7 |
|         |              | hex: 5    7    | hex  dec       | oct: 1  2   7   | oct   dec             |
|         |              |                |                |                 |                       |
|      60 |     00111100 | bin: 0011 1100 | 3C = 3*16 + 12 | bin: 00 111 100 | 074 = 0*8^2 + 7*8 + 4 |
|         |              | hex: 3    C=12 | hex  dec       | oct: 0  7   4   | oct   dec             |
|         |              |                |                |                 |                       |
|     226 |     11100010 | bin: 1110 0010 | E2 = 14*16 + 2 | bin: 11 100 010 | 342 = 3*8^2 + 4*8 + 2 |
|         |              | hex: E=14 2    | hex  dec       | oct: 3  4   2   | oct   dec             |
|---------+--------------+----------------+----------------+-----------------+-----------------------|

Several items are of note:

The same number is written in 4 forms, Decimal, Binary, Hexadecimal, and Octal
A single Hexadecimal digit ranges from decimal 0-15. Values larger than 9 are written as letters: A=10, B=11, C=12, D=13, E=14, F=15
Converting between Binary and Hexadecimal is easiest when grouping bits by 4: each 4 bits corresponds to one hexadecimal digit
Octal digits ranger from 0-7
Converting between Binary and Octal is easiest when grouping bits by 3: each 3 bits corresponds to one octal digit

5 Questions

Analyze the files in the provided codepack and answer the questions given in QUESTIONS.txt.

                           _________________

                            HW 04 QUESTIONS
                           _________________


Write your answers to the questions below directly in this text file to
prepare for the associated quiz. Credit for the HW is earned by
completing the associated online quiz on Gradescope.


PROBLEM 1: Memory Diagram
=========================

  Examine the code in dog_diagram.c which uses a couple simple functions
  with a struct.
  ,----
  |  1  #include <stdio.h>
  |  2  typedef struct{
  |  3    double weight;
  |  4    int age;
  |  5    char name[8];
  |  6  } dog_t;
  |  7  
  |  8  void init_dog(dog_t *d){
  |  9    strcpy(d->name, "Rolf");
  | 10    d->age = 0;
  | 11    d->weight = 5.0;
  | 12    ////// POSITION A
  | 13    return;
  | 14  }
  | 15  
  | 16  void birthday(int num, dog_t *d){
  | 17    int next = d->age + num;
  | 18    if(next < 3){
  | 19      d->weight += 10.0;
  | 20    }
  | 21    ////// POSITION B
  | 22    d->age = next;
  | 23    return;
  | 24  }
  | 25  
  | 26  int main(){
  | 27    dog_t dog;
  | 28    init_dog(&dog);
  | 29    double curwgt = dog.weight;
  | 30    birthday(2, &dog);
  | 31    printf("%s gained %f pounds\n",
  | 32           dog.name, dog.weight-curwgt);
  | 33    return 0;
  | 34  }
  `----

  Fill in the memory diagrams below for the layout of memory if
  execution stops at the positions given in the comments.


POSITION A
----------

  ,----
  | |------------+-------------+-------+-------|
  | | Frame      | Sym         | Addr  | Value |
  | |------------+-------------+-------+-------|
  | | main()     | curwgt      |       |       |
  | | line:28    | dog.name[7] |       |       |
  | |            |             |       |       |
  | |            |             |       |       |
  | |            |             |       |       |
  | |            |             |       |       |
  | |            |             |       |       |
  | |            |             |       |       |
  | |            |             |       |       |
  | |            |             | #1208 |       |
  | |            | dog.weight  | #1200 |   5.0 |
  | |------------+-------------+-------+-------|
  | | init_dog() | d           |       |       |
  | | line:??    |             |       |       |
  | |------------+-------------+-------+-------|
  `----


POSITION B
----------

  ,----
  | |------------+------------+-------+-------|
  | | Frame      | Sym        | Addr  | Value |
  | |------------+------------+-------+-------|
  | | main()     | curwgt     |       |       |
  | | line:??    |            |       |       |
  | |            |            |       |       |
  | |            |            |       |       |
  | |            |            |       |       |
  | |            |            |       |       |
  | |            |            |       |       |
  | |            |            |       |       |
  | |            |            |       |       |
  | |            |            | #1208 |       |
  | |            | dog.weight | #1200 |       |
  | |------------+------------+-------+-------|
  | | birthday() |            | #1192 |       |
  | | line:??    |            |       |       |
  | |            |            |       |       |
  | |------------+------------+-------+-------|
  | 
  `----


PROBLEM 2: Valgrind Debugging badmem.c
======================================

  The file badmem.c has functions main() and set_pn() in it but has a
  bad memory problem associated with it.  A sample compile and run is as
  follows.

  ,----
  | > gcc -g badmem.c
  | > a.out
  | Segmentation fault (core dumped)
  `----


A
~

  Below is some output from Valgrind. Explain the errors that are
  identified by Valgrind and inspect the source code of badmem.c to
  discover the source of the error. Clearly identify whether there is a
  problem in main() or set_pn().

  ,----
  | >> cat -n badmem.c                       # show code for badmem.c
  |      1	#include <stdio.h>
  |      2	#include <stdlib.h>
  |      3	
  |      4	
  |      5	// Struct to count positive/negative
  |      6	// numbers in arrays.
  |      7	typedef struct {
  |      8	  int poss, negs;
  |      9	} pn_t;
  |     10	
  |     11	void set_pn(int *arr, int len, pn_t *pn);
  |     12	// Scans through array arr counting positive/negative numbers and
  |     13	// adjusting the fields of the specified. Zero is considered a
  |     14	// positive number. If arr is NULL or len is less than 0, does not
  |     15	// change pn.
  |     16	
  |     17	int main(){
  |     18	  int arr1[5] = {3, 0, -1, 7, -4};
  |     19	  pn_t *pn1;
  |     20	  set_pn(arr1, 5, pn1);
  |     21	  // pn1: {.poss=3, .neg=2}
  |     22	  
  |     23	  int arr2[3] = {-1, -2, -4};
  |     24	  pn_t *pn2;
  |     25	  set_pn(arr2, 3, pn2);
  |     26	  // pn2: {.poss=0, .neg=3}
  |     27	
  |     28	  int *arr3 = NULL;
  |     29	  pn_t *pn3;
  |     30	  set_pn(arr3, -1, pn3);
  |     31	  // pn3: NULL
  |     32	
  |     33	  return 0;
  |     34	}
  |     35	  
  |     36	void set_pn(int *arr, int len, pn_t *pn){
  |     37	  if(arr==NULL || len < 0){
  |     38	    return;
  |     39	  }
  |     40	  pn->negs = 0;
  |     41	  pn->poss = 0;
  |     42	  for(int i=0; i<len; i++){
  |     43	    if(arr[i] < 0){
  |     44	      pn->negs++;
  |     45	    }
  |     46	    else{
  |     47	      pn->poss++;
  |     48	    }
  |     49	  }
  |     50	  return;
  |     51	}
  | 
  | >> gcc -gc badmem.c                      # compile with debug information
  | 
  | >> valgrind ./a.out                      # run compiled program under valgrind
  | ==15611== Memcheck, a memory error detector
  | ==15611== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
  | ==15611== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
  | ==15611== Command: ./a.out
  | ==15611== 
  | ==15611== Use of uninitialised value of size 8
  | ==15611==    at 0x10873B: set_pn (badmem.c:40)
  | ==15611==    by 0x1086B8: main (badmem.c:20)
  | ==15611== 
  | ==15611== Invalid write of size 4
  | ==15611==    at 0x10873B: set_pn (badmem.c:40)
  | ==15611==    by 0x1086B8: main (badmem.c:20)
  | ==15611==  Address 0x5 is not stack'd, malloc'd or (recently) free'd
  | ==15611== 
  | ==15611== 
  | ==15611== Process terminating with default action of signal 11 (SIGSEGV): dumping core
  | ==15611==  Access not within mapped region at address 0x5
  | ==15611==    at 0x10873B: set_pn (badmem.c:40)
  | ==15611==    by 0x1086B8: main (badmem.c:20)
  | ==15611==  If you believe this happened as a result of a stack
  | ==15611==  overflow in your program's main thread (unlikely but
  | ==15611==  possible), you can try to increase the size of the
  | ==15611==  main thread stack using the --main-stacksize= flag.
  | ==15611==  The main thread stack size used in this run was 8720384.
  | ==15611== 
  | ==15611== HEAP SUMMARY:
  | ==15611==     in use at exit: 0 bytes in 0 blocks
  | ==15611==   total heap usage: 0 allocs, 0 frees, 0 bytes allocated
  | ==15611== 
  | ==15611== All heap blocks were freed -- no leaks are possible
  | ==15611== 
  | ==15611== For counts of detected and suppressed errors, rerun with: -v
  | ==15611== Use --track-origins=yes to see where uninitialised values come from
  | ==15611== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)
  | Segmentation fault (core dumped)
  `----


B
~

  Fix badmem.c so that it works correctly. Your fix should NOT change
  the prototype for the set_pn() function but can make other adjustments
  to local variables.


PROBLEM 3: Number Conversions
=============================

A Unsigned Number Conversions
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

  Fill in the following table of equivalences.  Filling in the table
  from top to bottom is advantageous as earlier rows can sometimes be
  used to infer lower values. Feel free to make use of any ASCII table
  or the table.c program provided in the week 3 lecture code pack.

  ,----
  | |-----+------+-----+-----------+--------------|
  | | Dec | Hex  | Oct | Binary    | Char         |
  | |-----+------+-----+-----------+--------------|
  | |   9 | 0x09 |  11 | 0000 1001 | TAB          |
  | |  10 | ?    |   ? | ?         | \n (newline) |
  | |   ? | 0x20 |   ? | ?         | SPACE        |
  | |   ? | ?    |   ? | 0011 0010 | ?            |
  | |  65 | 0x41 | 101 | 0100 0001 | A            |
  | |  66 | ?    |   ? | ?         | ?            |
  | |   ? | 0x4F | 117 | ?         | O            |
  | |  80 | ?    |   ? | ?         | P            |
  | |  91 | ?    | 133 | 0101 1011 | [            |
  | |  97 | 0x61 | 141 | ?         | ?            |
  | |   ? | ?    | 172 | 0111 1010 | z            |
  | | 145 | 0x91 | 221 | ?         | none         |
  | | 160 | ?    |   ? | 1010 0000 | none         |
  | | 180 | 0xB4 | 264 | ?         | none         |
  | | 255 | ?    |   ? | ?         | none         |
  | |-----+------+-----+-----------+--------------|
  `----


B 32-bit Integer
~~~~~~~~~~~~~~~~

  Fill in the bits, hex, and decimal values for the given examples. The
  first example is completed for you. Assume all of these are 32 bit
  unsigned integers.
  ,----
  |   COMPLETED
  |   Binary:   0000 0000  0000 0000  0001 1000  1110 1001  
  |             0    0     0    0     1    8     E    9
  |   Hex   :   0018E9
  |   Decimal:  6377
  | 
  | 
  |   NUMBER 1
  |   Binary:   0000 0000  0010 1111  0011 1010  1000 1101  
  |             ?
  |   Hex   :   ??
  |   Decimal:  ??
  | 
  | 
  |   NUMBER 2
  |   Binary:   ??  
  |             7    F     8    3     5    A     0    B
  |   Hex   :   7F835A0B
  |   Decimal:  ??
  `----


C Signed Integer Conversions
~~~~~~~~~~~~~~~~~~~~~~~~~~~~

  Apply the steps involved in converting the following positive binary
  number to it's two's complement negation in 8-bit signed
  format. Recall the steps are
  - Invert the bits
  - Add one
  Apply these steps to the following number:
  ,----
  | 0111 1100  = 0x7C = 124 (decimal)
  `----

  The result is the two's complement representation of -124.

  Convert back to positive via the same process
  - Invert the bits
  - Add one
  to show that the original bits are gotten back.


D Signed Conversions Table
~~~~~~~~~~~~~~~~~~~~~~~~~~

  Complete the following table of equivalences assuming 8-bit
  twos-complement signed integers. The rightmost column is the inverse
  of the binary representation: flip 1's to 0's, and vice versa.

  ,----
  | |------+------+-----------+-----------|
  | |  Dec |  Hex | Binary    | Inverse   |
  | |------+------+-----------+-----------|
  | |   +5 | 0x05 | 0000 0101 | 1111 1010 |
  | |   -5 |    ? | 1111 1011 | ?         |
  | |  +32 | 0x20 | ?         | ?         |
  | |  -32 | 0xE0 | ?         | 0001 1111 |
  | | +127 | 0x7F | ?         | ?         |
  | | -127 | 0x81 | ?         | ?         |
  | | -128 |    ? | 1000 0000 | ?         |
  | |   +2 |    ? | ?         | ?         |
  | |   -2 | 0xFE | ?         | ?         |
  | |   +1 | 0x01 | 0000 0001 | ?         |
  | |   -1 |    ? | 1111 1111 | ?         |
  | |    0 |    ? | ?         | ?         |
  | |------+------+-----------+-----------|
  `----


E Overall Conversion Table
~~~~~~~~~~~~~~~~~~~~~~~~~~

  Complete the following table of conversions between CS numbering
  systems. The "Signed Decimal" column presumes the Two's Complement
  convention for number representation; review this with a TA if you are
  not clear on it.

  ,----
  | |-----+-----------+------+-------+----------+---------|
  | |     |           |      |       | Unsigned | Signed  |
  | | Num | Binary    |  Hex | Octal |  Decimal | Decimal |
  | |-----+-----------+------+-------+----------+---------|
  | |     |           |      |       |          |         |
  | |   1 | 1011 1000 |      |       |      184 |         |
  | |     |           |      |       |          |         |
  | |   2 |           | 0x80 |  0200 |          | -128    |
  | |     |           |      |       |          |         |
  | |   3 | 0011 0010 | 0x32 |       |       50 |         |
  | |     |           |      |       |          |         |
  | |   4 |           |      |  0234 |      156 |         |
  | |     |           |      |       |          |         |
  | |-----+-----------+------+-------+----------+---------|
  `----


PROBLEM 4: Best Score in File
=============================

  A grading file has scores for an exam formatted as in the following
  example:
  ,----
  | Darlene 91.0
  | Angela  76.5
  | Elliot  94.5
  | Tyrell  87.5
  | Dom     70.0
  | Phillip 55.5
  `----
  The names of students are the first item followed by a numeric score
  on their programming exam.  Write `main()' function in the file
  `best_score.c' which
  - Opens the file
  - Reads through all the contents
  - Prints out the name and score of the highest scorer

  Make use of the following small struct in this exercise to ease the
  process of copying information as indicated.
  ,----
  | typedef struct {
  |   char name[128];               // name of student
  |   double score;                 // score on exam
  | } grade_t;
  | // struct which allows assignment of name/score such as in
  | //   best = curgrade;
  | //   printf("best is now: %s %f\n", best.name, best.score);
  `----
  - Don't forget to close the file
  - Study the session below for special cases such as empty files

  ,----
  | > gcc -g best_score.c
  | > ./a.out 
  | usage: ./a.out <filename>
  | <filename> should have columns of names, numbers as in
  | Darlene 91.0
  | Angela  76.5
  | Elliot  94.5
  | Tyrell  87.5
  | Dom     70.0
  | Phillip 55.5
  | > ./a.out scores1.txt
  | Best score: Elliot 94.500000
  | > ./a.out scores2.txt 
  | Best score: Student13 90.800000
  | > ./a.out scores3.txt 
  | Best score: Student43 99.300000
  | > ./a.out scores-empty.txt
  | file was empty
  | > ./a.out no-such-file.txt
  | could not open the file
  `----