# CS31 Lab 1: Data Representation and Arithmetic Operations

Part 1 (written part):
due at the beginning of class Thursday Sept. 11

Part 2 (programming parts):
due by 11:59pm Thursday, Sept. 11

This lab assignment includes a written part that you will hand in at the beginning of class on Thursday and the programming part that you will submit electronically by Thursday evening using git. Use the setup31 script to create the appropriate directories for your first labs/01 homework folder. Note: if you did this already in lab, you can skip this step.

```  [~]\$ cd
[~]\$ setup31 labs/01
[~]\$ cd ~/cs31/labs/01
[~]\$ ls
Makefile  lab1.c
```
Now add the files you just copied to git. If you need to get the original copies back if you make a mistake, we can show you how to retrieve the files from git.
```  [~]\$ cd ~/cs31/labs/01
[~]\$ git commit -m "lab1 starter code"
[~]\$ git push
```

### Lab 1 Goals:

• To understand binary data representation of different types: int, unsigned, float, char
• To be able to convert between decimal, binary and hexadecimal representations
• To understand Binary arithmetic and apply it
• To understand bit-wise operations, and to use C bit-wise operators to manipulate binary data
• Practice with basic C programing and gdb

Part 1. Written Assignment
This part of the lab is a written assignment. You can either write-up your solutions by hand or write them up in vim (or emacs) and print the resulting file to one of our printers. To print a file created by vim (or emacs) on a CS lab printer use either enscript or lpr:
```\$ lpr filename
\$ enscript -2rG filename
```
If you write up your answers in vim (or emacs) 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. One way to ensure this is to work in a terminal 80 characters wide when you run vim so you can see when the currently line is too long and starts to wrap around. Typing in CNTRL-L in your file will print a page break:
```hello1     # this will print on the first page
^L         # this is typed in using CNTRL-L
hello2     # this will print on the second page
```

For these problems you are 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.

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 a 2's complement 8 bit number? Explain.
2. What is the largest positive value that can be represented with an unsigned 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 as unsigned 8 bit values? Does this operation result in overflow? If so, when?
2. What is the decimal representation of the resulting addition if the two values are unsigned 8 bit values?
3. What is the decimal representation of the resulting addition if the two values are signed 8 bit values?
4. What is the binary representation of the result of subtracting the second from the first as unsigned 8 bit values? 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 (2's complement) to 8 bit binary and to hexadecimal. Show your work:
1. 12
2. -36
3. 123
4. -123
9. (NOTE: We will cover these operators in class on Tuesday) 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

Part 2. C Programming
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 value(s) of COMPUTATION(s) that demonstrates your answer's correctness. DON'T just print something like this:
```   printf("The answer to question 1, what 0x2 + 0x6, is 0x8\n");
```
```   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 constructing some arithmetic expressions that will 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 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. What is the maximum positive value that can be stored in a C int variable? (write code that both gives the answer and proves/demonstrates your answer is correct)
2. What is the maximum value that can be stored in a C unsigned int variable?
3. What arithmetic operation is equivalent to left shifting an unsigned int value by 1?
4. What arithmetic operation is equivalent to left shifting an unsigned int value by 2?
5. What arithmetic operation is equivalent to right shifting an unsigned int value by 1?
6. If the value of an int expression evaluates to logical "true" in a C program, its bitwise NOT always evaluates to logical "false" in a C program (T or F)? C's bitwise NOT operator is ~ (e.g. y = ~x)

7. C's bit-wise OR and C's logical OR when applied to int or unsigned values both result in the identical logical results (i.e. (a || b) evaluates to true(false) iff (a | b) evaluates to true(false) for all values of a and b). (T or F)? Give at least two examples to support your answer.

C's bit-wise OR and C's logical OR when applied to the same two int or unsigned values both result in the identical int or unsigned values (i.e. the value of (a || b) is equal to the value of (a | b) for all values of a and b). (T or F)? Give at least two examples to support your answer.

8. C's bit-wise AND and C's logical AND when applied to the same two unsigned values always result in identical logical results (either both evaluate to true true or both to false) but do not necessarily evaluate to the same numeric values. (T or F)? Give at least two examples to support your answer.
```  l = x && y;  // && is C's logical AND operator
b = x & y;   // & is C's bitwise AND operator
```

#### Hints and Requirements for this part

• 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();
...
```
• Each answer should contain enough examples to support it. If your answer is "false", this usually means just providing a single counterexample that proves the statement false. If your answer is "true", then find a few different cases that demonstrate your claim. Do not, for example, enumerate every possible int value. For most questions, it should be enough to have 4 or 5 examples to support your answer. Do not have more than 10 for any one question.
• Remember, that because boolean values are represented as int values in C, you can assign the result of relational and logical operations to int variables to see the particular int value the expression:
```  int x;
x = (3 && 5)
printf("%d\n", x);
```
• Examples in support of your answer must be computed by the C program. For example, don't 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.
• Remember that type is important in C, and that if you use different formatting strings 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 should use good C programming style. See my "C Style Guide" for examples of commenting code and avoiding line-wrapping.
• For C programming help, see Prof. Newhall's C programming help/links page.
• Use the Makefile to build your program.

Submit

Use git add, git commit and git push to submit your changes. You should probably only need to add lab1.c

```  [~]\$ cd ~/cs31/labs/01
[01]\$ git commit -m "finished lab"
[01]\$ git push
```

I can only see and grade changes that you push. Git will only push changes you commit. Git will only commit things you add. Git command will only work in your ~/cs31/labs/01 directory, so be sure your are in the right path when you submit. Use git status to see if you need to perform any operations. Do not submit your compiled binary files. It is a best practice to run make clean before running git add. You can run git add, commit and push multiple times

Below is a detailed run of using git status to guide the changes you should make. Let's start by running make clean

```[~]\$ cd ~/cs31/labs/01
[01]\$ ls
lab1*  lab1.c  Makefile
[01]\$ make clean
rm -f lab1
[01]\$ ls
lab1.c  Makefile
```
Not the binary file lab1 was removed. That's OK. It is built automatically and so we don't need to save changes to that file or maintain it under version control. You only need to add and commit source files like .c, .h, .txt, or Makefiles. Let's run git status and see what we need to do.
```[01]\$ git status
On branch master

Changes not staged for commit:
(use "git add ..." to update what will be committed)
(use "git checkout -- ..." to discard changes in working directory)

modified:   lab1.c

no changes added to commit (use "git add" and/or "git commit -a")
```
Oh, we made changes to lab1.c. Since that probably has the solutions to our lab assignment, we should definitely add, commit, and push that. Start with git add and check the status
```[01]\$ git add lab1.c
[01]\$ git status:
On branch master

Changes to be committed:
(use "git reset HEAD ..." to unstage)

modified:   lab1.c

```
So now git sees that changes to lab1.c are ready to commit. We just need to run git commit with a descriptive message of what we did.
```[01]\$ git commit -m "finished lab"
[master 2102244] finished lab
1 file changed, 1 insertion(+), 1 deletion(-)
[01]\$ git status
On branch master
(use "git push" to publish your local commits)

nothing to commit, working directory clean
```
The new status says there is nothing to commit, which is a good sign. It also says that we are ahead of 'origin/master' by 2 commits., meaning we are out of sync with the git repository that the instructor can see. Let's push so we can get credit for our hard work.
```[01]\$ git push
Counting objects: 8, done.
Delta compression using up to 16 threads.
Compressing objects: 100% (6/6), done.
Writing objects: 100% (6/6), 584 bytes | 0 bytes/s, done.
Total 6 (delta 4), reused 0 (delta 0)
b86bb63..2102244  master -> master
[01]\$ git status
On branch master
Your branch is up-to-date with 'origin/master'.

nothing to commit, working directory clean
```
These last three lines of "up-to-date" and "nothing to commit" are what we want to see. Note it may be ok if you are "up-to-date" but have some "Untracked files". This usually happens when you have the binary executable lab1 in your directory.
```[01]\$ make
[01]\$ ls
lab1*  lab1.c  Makefile
[01]\$ git status
On branch master
Your branch is up-to-date with 'origin/master'.

Untracked files:
(use "git add ..." to include in what will be committed)

lab1

nothing added to commit but untracked files present (use "git add" to track)
```
lab1 is untracked, but since it a binary, automatically generated file, we should not add it to out get repo. The basic rule is if a file goes away when you run make clean it should not be in the git repository.