Due by 11:59 pm, Friday, September 13, 2024

Part 0: Midterm Agreement form. Hardcopy, filled in and signed Thursday, Sept. 12 in class.

NOTE: typically labs will be due Wednesday, but we are giving you a little extra time on this due to the course introduction and the timing of binary lectures. However, we encourage you to complete this lab before your Thursday/Friday lab when we will assign Lab 2.

If androids someday DO dream of electric sheep
Figure 1. Can’t Sleep (https://xkcd.com/571/). If androids dream of electric sheep, don’t forget to declare sheep_count as an unsigned long long.

1. Lab Overview

This lab gives you practice with binary representation and binary arithmetic operations. It includes a written problem set (Part 1) and a programming exercise (Part 2). Both parts will be submitted electronically using git.

2. Lab Goals

  • Explore the binary data representation of different types: int, unsigned, float, and char.

  • Convert between decimal, binary, and hexadecimal representations.

  • Apply arithmetic operations to binary numbers.

  • Manipulate binary data with C bit-wise operators.

  • Practice with C programming and using the gdb debugger.

  • Practice using the Vim editor.

3. Getting Lab 1 Starting Point Code

For CS31 lab assignments, you will use git to grab your lab starting point code, to submit your lab solution, and to save partial work along the way. In subsequent labs you will also use git to share lab code with your partner.

For each lab assignment you will do the following:

  1. Get the ssh-URL to your Lab git repository from the GitHub server for our class: CS31 github org

  2. Using your URL, and from your cs31/labs/ subdirectory, run git clone to clone a local copy of your repo:

    machine[~]$ cd ~/cs31/labs/
machine[labs]$ git clone [the ssh-URL to your your Lab1 repo]

  3. cd into your lab repo and work on the lab assignment. Often starting by opening the README.adoc file is a good place to start, as it will give some information about the starting point files.

    machine[labs]$ cd Lab1-userID1
machine[Lab1-userID1]$ ls
 lab1.c  Makefile  part1.txt  README.adoc
machine[Lab1-userID1]$ vim README.adoc

This week, we will go through these above general steps in more detail in the weekly lab session. The detailed steps are also listed at the beginning of this page: setup for CS31 lab assignments.

4. Part 0. Midterm agreement form

Midterm Agreement Form

5. Part 1. Problem Set

This part of the lab is a written assignment. You will write your solutions using the Vim editor to the set of questions below in the part1.txt file. You can review the Lab 0 page for vimtutor lessons and Vim resources.

$ cd ~/cs31/labs/Lab1-userID1
$ pwd
/home/you/cs31/labs/Lab1-userID1
$ vim part1.txt

5.1. Requirements

  • The answers to Part 1 should be entered in the part1.txt file using the vim editor.

      $ vim part1.txt

  • For these questions you will be graded on showing how you applied the operation or conversion method we described in class: you must show your work or explain how you got the result to receive credit.

    You can check your answers for correctness by using GDB’s print command. See the weekly lab 1 page for details on using GDB as a calculator.

  • The file contains some directions at the top for how to format certain numeric values, namely:

    • for superscript use ^, so 2^4 is 24 ("two to the fourth power").

    • for subscripts use a number after a variable, so X3 is X3 ("X sub 3").

    • for hexadecimal values, use the 0x prefix, so 0x123a is hexadecimal value "123a". Use lowercase letters when writing hexadecimal digits a-f.

    • for binary values, use the 0b prefix, so 0b101010 is binary value "101010".

    • for decimal values, use no prefix, so 10431 is decimal value "10,431".

  • If a question specifies a number of bits, your answer should be in a corresponding number of digits.

    • For example, to add two 4-bit values together your answer should be a 4-bit value, not a 64-bit one!

  • You may assume that two’s complement is used for signed values, which makes the high-order bit an indication of the value’s sign.

    • For example, 1000 should be interpreted as negative when treated as a 4-bit signed value (high-order bit is 1). But when interpreted as an 8-bit signed value (00001000) it is positive (high-order bit is 0).

  • No Line Wrap: as you type in your answers, make sure to not have lines longer than 80 characters (explicitly hit the Enter key to start a new line). If you have lines longer than 80 characters they will either appear to be cut off or wrapped strangely. I suggest making your editor window exactly 80 characters wide so that you can see when the current line is too long and starts to wrap around.

5.2. The Questions

Answer the questions below showing your work and/or explaining your answer.

  1. What is the largest positive value that can be represented with an unsigned 8 bit number? Explain.

  2. What is the largest positive value that can be represented with a 2’s complement 8 bit number? Explain.

  3. Convert the unsigned 8 bit binary value 0b10100110 to decimal. Show your work.

  4. Convert the signed 8 bit binary value 0b10100110 to decimal. Show your work.

  5. For the following 8 bit binary values (show your work):

    value 1: 01011101
value 2: 01101101

    1. Add the binary values together. What is the decimal representation of the result if it is interpreted as a signed 8 bit value?

    2. For the same addition, what is the decimal representation of the result if it is interpreted as an unsigned 8 bit value?

  6. Convert the following 2-byte binary numbers to hexadecimal, indicating how each part is converted (the binary values are shown with spaces between each 4 digits just to make them easier to read):

    1. 0000 0110 0001 1111

    2. 1100 0101 1110 0101

    3. 1010 0111 1101 0110

  7. Convert the following hexadecimal numbers to binary, indicating how you converted each digit:

    1. 0x23

    2. 0x852

    3. 0xc1a6

    4. 0xefab

  8. Convert the following decimal values to 8 bit (2’s complement) binary and additionally convert the binary results to hexadecimal. Show your work:

    1. 12

    2. -36

    3. 123

    4. -123

We suggest you wait to try these until after we have covered section 4.5: overflow and section 4.6: bit-wise operators in lecture:

  1. For the following 8 bit binary values (show your work):

    value 1: 01011101
value 2: 01100101

    1. What is the binary representation of the result of adding value1 and value2 together? Does this operation result in overflow? If so, under what interpretation of the values (signed/unsigned)?

    2. What is the binary representation of the result of subtracting the value2 from value1? Does this operation result in overflow? If so, under what interpretation of the values (signed/unsigned)?

  2. Given the following 4 bit binary values, show the results of each bit-wise operation, showing both the binary and decimal result value for each (list the unsigned decimal value):

    1. 0110 | ~(1010)

    2. ~(0110 | 1010)

    3. 0111 & ~(1001)

    4. (1010 | 0000) & 1111

    5. 0011 ^ 1110

    6. 0111 << 2

    7. 0111 >> 2

6. Part 2. C Programming

For this part, you will write a single C program (lab1.c) that when run, prints out answers to each of the questions listed below.

For each question, you will write a function that prints out your answer to the question, and that prints out some expressions and their results that support your answer to the question. For example, the beginning of a run of your program might look like this:

$ ./lab1
Question 1: my answer to question 1 is ...
    This can be verified by examining the result of the expression ...
    when x is the int value ... and y is ... the expression is ...
    when x is ... and y is ... the expression is ...

Question 2: my answer to question 2 is ...
    This can be verified by ...

6.1. Requirements

  • The answers to Part 2 should be implemented in the lab1.c program, and when compiled and run, should output answers to each part. Use the vim editor to edit the lab1.c file:

    $ vim lab1.c

  • Your C program, when run, should print out the answer to each question in order, with supporting examples, in an easy to read format. Use formatted printf statements, and do not print out lines that are longer than 80 characters (break long output up into multiple printf statements). Look at printf examples in Week 1 in-lab examples.

  • The answer to each question should be implemented as a separate function called by main. For example, your code and main might look like:

    // function prototypes: declare function's name and type
void question1(void);
void question2(void);
void question3(void);
...
// main function:
int main() {
  ...
  question1();  // call the question1 function
  question2();
  ...
}
...
// function definitions: their implementations
void question1(void){
  ...
  //example print statement (not the actual statement you would write)
  printf("The sum of %d and %d is %d", x, y, x+y);
}

    You are welcome to add additional helper functions!

  • Each answer should contain necessary and sufficient examples to support it. Do not, for example, enumerate every possible int value.

    • For most questions, it should be enough to have 3 to 5 examples to support your answer. Do not have more than 10 for any one question.

    • For questions 3 and 4, you don’t really need more than one example if your example clearly demonstrates that your claim is true.

  • Examples in support of your answer must be computed by the C program. For example, do not just print out the string "3 + 6 = 9" instead write C code that computes the expression and prints out its result, like this:

    int x, y;

x = 3;
y = 6;
printf ("%d + %d = %d\n", x, y, (x+y));

  • Each answer should include printing out the result(s) of computation(s) that demonstrates your answer’s correctness. DO NOT just print something like this:

    printf("The answer to question 0, what 0x3 + 0x6, is 0x9\n");

    Instead, have C code that computes the answer to show or to prove that your answer is correct:

    unsigned x, y, z;

x = 0x3;   // you can initialize a variable to a hex value using prefix 0x
y = 0x6;
z = x + y;
printf("The answer to question 1, what %x + %x is %x\n", x, y, z);

    For some questions, the code proving your answer correct may be as simple as the example above. For others, however, you will have to think about how to construct some a sequence of arithmetic expressions that demonstrate the correctness of your answer (or show that the converse is false).

    You may want to first try printing some values and expressions in gdb in binary, hexadecimal, and decimal to help you figure out good values to test in your C program to ensure you are considering all cases, and to find good examples to use to demonstrate correctness in your answer. See the week 1 weekly lab page for more information about using gdb as a calculator.

  • Your code should be commented, modular, robust, and use meaningful variable and function names. This includes having a top-level comment describing your program and listing your name.

    Look for the TODO: comments in the in the lab1.c file for what to add and where. You should follow the examples of the first two question functions as you add in and call new functions for the other questions.

  • No Line Wrap: you code should not contain lines that are longer than 80 characters. If you have lines longer than 80 characters they will either appear to be cut off or wrapped strangely in your lab print-out.

    For example, you can break up a single printf with a very long format string into multiple calls to printf:

       // replace this:
   printf("This string is way too long, wider than %d characters, which will make a printout super hard to read!\n, 80);

   // with two calls to printf, each printing part:
   printf("This string is way too long, wider than %d characters, ", 80);
   printf("which will make a printout super hard to read!\n);

   // and this long message is also better printed out in two lines, so
   // these two calls to printf are even better (note additional \n):
   printf("This string is way too long, wider than %d characters,\n", 80);
   printf("which will make a printout super hard to read!\n);

    See the C code style guide for some other examples of how to keep lines at no more than 80 chars wide.

    I also suggest making your editor window exactly 80 characters wide so that you can see when the current line is too long and starts to wrap around.

6.2. The Questions

Answer these questions by writing a C program that prints out the answer and prints out example expression(s) that support your answer:

  1. Given the following variable declaration and initialization, show how you can use 3 different format strings in printf to display the value of val in different ways.

    Hint: If you aren’t sure how to proceed, try taking a look at the example format specifiers from the {weeklylab}[Week 1 Weekly Lab page].

    int val;
val = 97;

  2. For the two variables and their initializations shown below, what is their sum in hex? And, is the resulting sum a positive or negative value?

    int x, y;

x = 0x98765432;  // you can init var to hex value by adding prefix 0x
y =   98765432;

If you get stuck on these two, you may want to come back to them after we have covered section 4.5: overflow in lecture:

  1. What is the maximum value that can be stored in a C unsigned int variable (unsigned)?

  2. What is the maximum positive value that can be stored in a C int variable (signed)?

We suggest you wait to try these until after we have covered section 4.6: bit-wise operators in lecture:

  1. What arithmetic operation is equivalent to left shifting an unsigned int value by 1?

  2. What arithmetic operation is equivalent to left shifting an unsigned int value by 2?

  3. What arithmetic operation is equivalent to right shifting an unsigned int value by 1?

7. Tips (for both parts)

  • Remember that type is important in C!

    • If you give different formatting codes to printf, you can print out the same value as different types (for example, printing a value as %c looks different than printing it as %d).

    • If you are not seeing the values that you expect to see, check your printf format string and use gdb to examine your running program.

  • printf: if you need some help with printf print formatting

    • Look at printf examples from Week 1 in-lab examples.

    • For more information, look at printf examples in the textbook here and here to use nice formatting for any tabular output your program might produce.

  • Make use of GDB as a calculator. See the week 1 in-lab page for information about using gdb as a calculator.

    • For Part 1 (written), you can check the correctness of most of your answers using GDB.

    • For Part 2 (C program), you may want to try printing some values and expressions in gdb in binary, hexadecimal, and decimal to help you figure out good values to test to come up with your answer and to show/prove that your answer is correct.

  • Vim: review the Lab 0 page for vimtutor lessons and Vim resources.

  • printing: you will turn in all of your code electronically, but if you want to print out a copy of your answers to view off-line, use the lpr command in the shell, which will print to the lab machine in the lab room you are using. You will turn your files in electronically, so you don’t need to print them.

    $ lpr part1.txt
$ lpr lab1.c

    The file will print out to the printer in the lab in which you are working. Please be careful to not leave printouts of your solutions in the lab printers per the department’s Academic Integrity rules. Also do NOT print binary files (your compiled programs). If you accidentally do, you can use lprm to remove a printer job.

    $ lprm

  • As you add content, we suggest you add and commit your partial changes to your repo:

    $ git add part1.txt
$ git commit -m "answers 1-4"

8. Submitting your Lab

Please remove any debugging output prior to submitting.

To submit your code, commit your changes locally using git add and git commit. Then run git push while in your lab directory.

Also, it is good practice to run make clean before doing a git add and commit; you do not want to add to the repo any files that are built by gcc (e.g. executable files). Included in your lab git repo is a .gitignore file telling git to ignore these files, so you likely won’t add these types of files by accident. However, if you have other gcc compiled binary files in your repo, please be careful about this.

Here are the commands to submit your solution (from your ~/cs31/Labs/Lab1-userID1 directory):

$ make clean
$ git add part1.txt
$ git add lab1.c
$ git commit -m "correct and well commented Lab1 solution"
$ git push

Verify that the results appear (e.g., by viewing the the repository on CS31-f24). You will receive deductions for submitting code that does not run or repos with merge conflicts. Also note that the time stamp of your final submission is used to verify you submitted by the due date or by the number of late days that you used on this lab, so please do not update your repo after you submit your final version for grading.

If you have difficulty pushing your changes, see the "Troubleshooting" section and "can’t push" sections at the end of the Using Git for CS31 Labs page. And for more information and help with using git, see the git help page.

After you submit your solution for grading, you should fill out and submit the required (NOTE: not required for lab 1)[Lab 1 Questionnaire].

9. Handy Resources