CS 208 s21 — Integer Arithmetic

Table of Contents

1 Warmup

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

  • 0b00001001 = 9
  • 0b10000001 = -127

2 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\)
  • this is handy because it means the same hardware can perform both signed and unsigned addition

3 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

3.1 Fixed-width arithmetic is modular

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

twos-complement-modular.png

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.

4 Sign Extension

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)
  • 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).

5 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)