# CSCI 2021 Lab03: Binary Integers

**Due: 11:59pm Tue 9/24/2019***Approximately 0.83% of total grade*- Lab exercises are open resource/open collaboration. You must submit your own work but you may freely discuss lab topics with other members of the class.

#### CODE DISTRIBUTION: lab03-code.zip

- Download the code distribution every lab
- See further setup instructions below

#### CHANGELOG:

## 1 Rationale

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 lab. C provides facilities to manipulate data at the bit level using logical and shift operations which are also discussed.

### Associated Reading / Preparation

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 lab is earned by taking the associate Lab Quiz which
is linked under `Canvas / Assignments`

. The quiz will ask that you upload
your completed `QUESTIONS.txt`

document and then take a short quiz on
the material covered in the lab.

See the full policy in the syllabus.

## 2 Codepack

The codepack for the lab contains the following files:

File | Description |
---|---|

`QUESTIONS.txt` |
Questions to answer |

`convert.c` |
C file for Problem 3 |

`twos_complement.c` |
Simple demonstration of C code for twos complement |

## 3 Two's Complement Arithmetic

Your lab leader will discuss the basics of two's complement
representation of integers at the beginning of the lab. Understanding
two's complement is necessary to complete a problem `QUESTIONS.txt`

.

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 be0101 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:

- Invert the bits: ones become zeros, zeros to ones. The C operator
invert is the tilde
`~`

symbol. - 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.- Invert the bits: ones become zeros, zeros to ones. The C operator
invert is the tilde
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 What to Understand

Ensure that you understand

- Signed vs unsigned representations
- Two's complement representation of integers
- Conversions between binary, decimal, octal, and hexadecimal notation

## 5 Questions

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

.

__________________ LAB 03 QUESTIONS __________________ - Name: (FILL THIS in) - NetID: (THE kauf0095 IN kauf0095@umn.edu) Answer the questions below according to the lab specification. Write your answers directly in this text file and submit it to complete the lab. PROBLEM 1: Number conversions ============================= A ~ 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 ~ 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: ?? `---- PROBLEM 2: Signed Integer Conversions ===================================== A ~ 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. B ~ 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 | ? | ? | ? | | |------+------+-----------+-----------| `---- PROBLEM 3: Converting Strings to Numbers ======================================== Inspect the program in the lab pack called `convert.c'. Compile and run it using ,---- | > gcc convert.c | > ./a.out `---- Describe briefly what kind of conversion is being done by the `convert()' function given. - A. What kind of data is input? - B. What result is produced by the function? - C. How is a success versus an error reported? - D. Why is this kind of conversion needed? - E. What built-in C function (useful for the assignment) does this conversion function use and how is its calling convention different from convert()?

## 6 Again, What to Understand

Ensure that you understand

- Signed vs unsigned representations
- Two's complement representation of integers
- Conversions between binary, decimal, octal, and hexadecimal notation