Due Date

  • Due: Thursday, Sept 12, 11:59 PM. Submit using git (see Section 8 for instructions). We are giving you a little extra time on this one, but encourage you to complete it before Wednesday lab when we will assign Lab 2.

If androids someday DO dream of electric sheep

1. Lab1 Goals:

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

  • To convert between decimal, binary and hexadecimal representations.

  • To apply binary arithmetic.

  • To apply C bit-wise operators to manipulate binary data.

  • Practice with C programming, the gdb debugger, and the vim editor.

2. Lab Description

This lab assignment includes a written problem set (Part 1) and a programming exercise (Part 2). Both parts will be submitted electronically by Thursday evening using git.

3. Getting Lab1 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:

      $ cd ~you/cs31/labs/
      $ git clone [your-Lab1-ssh-URL]
  3. cd into your lab repo and work on the lab assignment. Often starting by opening the README.md file is a good place to start, as it will give some information about the starting point files.

  $ cd lab1-you
  $ ls
    Makefile  README.md  lab1.c  part1.txt
  $ vim README.md

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

4. Part 1. Problem Set

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

vim part1.txt

Add your name and email to the top of this file.

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

  • for superscript use ^, so 2^4 is 2 to the fourth power.

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

  • for hexadecimal values, use the 0x prefix, so 0x123a is hexadecimal value 123a.

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

  • for decimal values, use no prefix, so 10101 is decimal value 10,101.

Also, 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 be cut off by the printer or wrapped strangely. I suggest running vim in a window that is is exactly 80 characters wide so that you can see when the current line is too long and starts to wrap around.

If you want to print out a copy of your answers to view off-line, use the lpr command in the shell (not from vim):

lpr part1.txt

As you add content, you may want to add and commit partial changes to your repo:

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

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. Check your answers for correctness by either writing a C program to do some of the computation and printing result values or by using gdb’s print command. See the weekly lab page for details on using gdb.

Part 1 Questions

Answer the questions below showing your work and/or explaining your answer. For these questions, if a question specifies a number of bits, your answer should be in a corresponding number of digits. For example, if the question asks to add 4 bit values together your answer should be a 4 bit value, not a 64 bit one. Also, assume that for signed values, the high-order bit is the sign bit. For example, 1000 should be interpreted as negative as a 4-bit signed value, but positive as an 8-bit signed value (00001000).

  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 10100110 to decimal. Show your work.

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

  5. 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 them together? Does this operation result in overflow? If so, when (i.e., under what circumstances / interpretations of the values)?

    2. What is the decimal representation of the resulting addition if the two values are signed 8 bit values?

    3. What is the decimal representation of the resulting addition if the two values are unsigned 8 bit values?

    4. What is the binary representation of the result of subtracting the second from the first? Does this operation result in overflow? If so, when?

  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 to hexadecimal. Show your work:

    1. 12

    2. -36

    3. 123

    4. -123

  9. 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

5. Part 2. C Programming

For this part, you will write a single C program that when run, prints out answers to each of the questions below. For each question, print out a string that is your answer to the question, and then print 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 ...

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 1, what 0x2 + 0x6, is 0x8\n");

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

unsigned x, y, z;
x = 0x2; 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 arithmetic expressions that demonstrate the correctness of your answer.

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 in your C program to ensure you are considering all cases.

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

  1. (Optional Question: you are not required to answer this question, but we encourage you to try it out first, in part because the start of its implementation is in lab1.c):

    Given the following variable declaration and initialization, how many ways can printf display the value of x? Show at least 4 different ways.

    unsigned int x;
    x = 97;
  2. What is the maximum value that can be stored in a C unsigned int variable (unsigned)?

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

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

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

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

6. Requirements

Part 1

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

      $ vim part1.txt
  • Lines should be no longer tha 80 characters (use the "Enter" key to explicitly add line break, and run vim in a window that is 80 chars wide):

Part 2

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

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

    int main() {
      question1();  // call the question1 function
      question2();
      ...
    }

    You are welcome to add additional helper functions.

  • Each answer should contain enough 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 2 and 3, 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));
  • 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 lines). Look at printf examples and documentation to use nice formatting for any tabular output your program might produce.

  • 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. In addition, every function should include a brief description of its behavior.

7. Tips

  • Remember that type is important in C, and that if you give different formatting codes to printf, you can print out the same value as different types (for example, if you print out a value using %u you may see a very different value that if you print it out using %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.

  • You can print ascii files on our system using lpr command:

    lpr part.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 (a.out’s). If you accidentally do, run lprm to remove a printer job.

8. Submitting

  • Please remove any debugging output prior to submitting.

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

    git add lab1.c
    git add part1.c
    git commit -m "lab 1 is done"
    git push

    You can run these commands any number of times before the due date to update your solution answers in the remote master. In fact, it is good practice to solve some of the lab, do an add, commit, and push, then solve more, …​

    Running git status will show if you have any local changes to files that need to be committed.

At the due date I will pull your solutions from the remote master git repo and grade those. I can only see and grade changes to your Lab1 Git Repo that you push. Git will only push changes you commit. Git will only commit things you add.

It is also good practice to not modify your Lab source code (lab.c) after the due date. If something goes wrong, I’ll use the modification date of the file in your local repo to determine which version of your solution you submitted before the due date.

For more info, see the section on Using a git repo on the git help page, and see the README.md file in your lab repo.

9. Handy Resources