Recitation 03: Integers

• Handout [Solution]
• Integers and Twos Compliment Representation.
• If we have a binary number with n bits represented as $b_{n-1}b_{n-2} \ldots b_2b_1b_0$, we can calculate its decimal value as: $$-b_{n-1} \times 2^{n-1} + \sum_{i=0}^{n-2} b_i \times 2^i$$
• A few slides borrowed from 15-213 with some helpful graphics to help visualize int properties (some will actually be relevant to Friday).
• Discussed bitwise not (~) and the property that $-x = \sim x + 1$.

---

Checking for Overflow

To follow up on the example from the handout, it turns out that when adding two numbers, positive overflow will give a negative number and negative overflow will give a positive number. However, this is not a universal check. Suppose I have some expression along the lines of

int x = // Some mathematical expression that might cause positive overflow.

It is NOT universally true that I can check for overflow with

if (x < 0)
  println("OVERFLOWBAD!");

This was okay when we were checking for overflow when we were adding two numbers. Since overflow obeys modular arithmetic, it is the case that overflow here will always give a negative number. In other cases, the expression being evaluated can wrap back around to positive numbers.

For example, these both overflow:

      Coin 0.3.1 'Nickel' (r108, Wed Aug 29 08:36:24 EDT 2012)
      Type `#help' for help or `#quit' to exit.
      --> 0x7fab36c1 * 3;
      2130814019 (int)
      --> 0x7e829512 + 0x7fabbaef + 0x7e111111;
      2084528402 (int)

In general, a good way to think about overflow is to catch it before it happens, rather than trying to reason about it after the fact. For example, another way we can check for overflow when adding two positive numbers x + y is

if (x > int_max() - y) // Comes from rearranging x + y > int_max(), which we can't actually check.
  println("OVERFLOW");
else
  // Do something.

Notice that I was able to check for overflow without ever adding x and y. This reasoning can be generalized to apply to other situations. Here int_max() is a function defined in the C0 util library, returning the maximal integer.

If you have any comments or see any errors, please let me know.