# CS 208 s20 — Integer Arithmetic

## Table of Contents

## 1 Homework Solutions

### 1.1 Sign and Magnitude vs Two's Complement Discussion

- I agree with the point several of you made on the discussion forum that sign and magnitude is more intuitive/easier for humans to deal with by hand. It's probably the first thing I would think of to represent negative binary numbers.
- As many of you pointed out, sign and magnitude two representations of zero (
`0b0000`

and`0b1000`

—negative zero??)- In addition to complications from having two, non-equal versions of 0, this wastes one out of our 16 possible values

- Perhaps more importantly, arithmetic is cumbersome as negatives "increment" in the wrong direction (i.e., adding +1 to a negative number makes it more negative)

- Two's complement fixes the problems with sign and magnitude
- negative numbers "flipped" so that incrementing does what we want
- no more -0

- It also preserves nice property of sign and magnitude that positive encodings match unsigned encodings
- Note that the most significant bit end up still indicating the sign!

Considering 8-bit integers:

- What is the largest integer?
Unsigned: Two's Complement: 255 127 - How do you represent (if possible) the following numbers: 39, -39, 127?
Unsigned Two's Complement `39`

:`0b00100111`

`39`

:`0b00100111`

`-39`

: not possible`-39`

:`0b11011001`

`127`

:`0b01111111`

`127`

:`0b01111111`

## 2 Warmup

What base-10 integers do these 8-bit quantities represent using two's complement?^{1}

`0b00001001`

`0b10000001`

`0b11111111`

`0b00001111`

## 3 Two's Complement Arithmetic

- the same procedure works for both unsigned and two's complement addition
- add the bits as you would expect, discard any that carry out of the most significant bit
- example: \(4 + (-3)\) =
`0100 + 1101`

=`10001`

=`0001`

= \(+1\)

- example: \(4 + (-3)\) =

- add the bits as you would expect, discard any that carry out of the most significant bit
- this is handy because it means the same hardware can perform both signed and unsigned addition

### 3.1 Practice

Verify that binary addition produces the correct two's complement result for these expressions:^{2}

- \(-2 + -3\)
- \(2 + -3\)

### 3.2 Additive inverse

Important that for all \(x\), the bit representation of \(x\) and the bit representation of \(-x\) sum to 0 (\(mod\ 2^w\)).
That is, it had better be the case that \(x + (-x) = 0\) (throwing away any bits that carry out off the left side)
Find the 8-bit negative encodings for these three bit vectors and verify that the sum of the two is 0:^{3}

`0b00000001`

`0b00000010`

`0b11000011`

Additive inverses are well behaved for two's complement. We'll see how to quickly find the additive inverse in binary in Friday's topic.

## 4 Overflow

- Overflow occurs when the result of a computation can't be represented by the current encoding
- For example, \(6 + 3\) =
`0110 + 0011 = 1001`

= \(-7\)- The expected result of \(6+3=9\) exceeds the range of positive numbers 4-bit two's complement can represent

### 4.1 Fixed-width arithmetic is *modular*

When we have a fixed number of bits (e.g., 4-bit two's complement), arithmetic becomes *modular*.

The result of an addition is the sum *modulo* \(2^w\) (in raw binary—it's then up to the program whether the result is interpreted as signed or unsigned).
Intuitively, think of fixed-width arithmetic as *wrapping around* when it goes too positive or too negative.
With 4-bit two's complement, subtract 1 from -8 and it *overflows* to +7.
Similarly, add 1 to +7 and it overflows to -8.

Here we finally see why `int x = 200 * 300 * 400 * 500`

results in a large negative value.
The result of the multiplication overflows the largest positive value than can be represented by a 32-bit `int`

and wraps around into negative values.

## 5 Sign Extension

Which of the following 8-bit numbers has the same signed (2's complement) value as the 4-bit number `0b1100`

?^{4} (spaces added for readability)

`0b 0000 1100`

`0b 1000 1100`

`0b 1111 1100`

`0b 1100 1100`

**When converting signed integer to a larger integral type, extend with copies of the most significant bit (i.e., sign bit)**

- 4-bits to 8-bits:
- 5 goes from
`0101`

to`00000101`

(still 5) - -5 goes from
`1011`

to`11111011`

(still -5)

- 5 goes from
- Called
*sign extension*because we maintain the same value by extending the sign bit to fill in the new bits- This is what C will do if you cast a smaller signed integer type to a larger one (i.e., cast an
`int`

to a`long`

) - Casting unsigned types does not perform sign extension, the new bits are filled with zeros (
*zero extension*).

- This is what C will do if you cast a smaller signed integer type to a larger one (i.e., cast an

## 6 Truncation

One the other hand, going from a larger integer type to a smaller one just throws away (*truncates*) the extra bits.

- 8-bits to 4-bits:
- 23 goes from
`00010111`

to`0111`

(now 7) - -23 goes from
`11101001`

to`1001`

(now -7)

- 23 goes from

## 7 Homework

- Read section 2.2.8
*Advice on Signed vs Unsigned*in the CSPP book (p. 83–84) and do practice problems 2.25 and 2.26- These highlight the practical application of understanding integer representations

- CSPP practice problem 2.29 (p. 93)
- They use \(+\) to mean "normal" addition (not modular) and \(+_5^t\) to mean 5-bit two's complement addition
- The
*case*refers to the for possibilities in Figure 2.24- \(x + y\) is negative and \(x +_5^t y\) overflows to a positive result
- \(x + y\) is negative and \(x +_5^t y\) does not overflow (also negative)
- \(x + y\) is positive and \(x +_5^t y\) does not overflow (also positive)
- \(x + y\) is positive and \(x +_5^t y\) overflows to a negative result

- Start lab 0! For real! No joking around!
- Remember that the Week 1 quiz must be completed by 9pm April 15.

## Footnotes:

^{1}

Convert these bit vectors to decimal integers using two's complement

`0b00001001`

= 9`0b10000001`

= -127`0b11111111`

= -1`0b00001111`

= 15

^{2}

Verify binary addition produces the correct result:

- \(-2 + -3 =\)
`0b1110 + 0b1101`

1 | 1 | 1 | 0 | |
---|---|---|---|---|

+ | 1 | 1 | 0 | 1 |

1 | 1 | 0 | 1 | 1 |

_ | 1 | 0 | 1 | 1 |

final result: `0b1011`

= \(-5\)

- \(2 + -3 =\)
`0b0010 + 0b1101`

0 | 0 | 1 | 0 | |
---|---|---|---|---|

+ | 1 | 1 | 0 | 1 |

1 | 1 | 1 | 1 |

final result: `0b1111`

= \(-1\)

^{3}

Find the additive inverses, verify the sum is 0:

`0b00000001`

= 1, inverse is \(-1\) =`0b11111111`

1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
---|---|---|---|---|---|---|---|---|

+ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |

1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

_ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

`0b00000010`

= 2, inverse is \(-2\) =`0b11111110`

1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | |
---|---|---|---|---|---|---|---|---|

+ | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |

1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

_ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

`0b11000011`

= \(-61\), inverse is \(61\) =`0b00111101`

1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | |
---|---|---|---|---|---|---|---|---|

+ | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |

1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

_ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

^{4}

What is the 8-bit equivalent of `0b1100`

(\(-4\))

`0b 0000 1100`

is 12`0b 1000 1100`

is \(-116\)`0b 1111 1100`

is \(-4\) (correct answer)`0b 1100 1100`

is \(-52\)