## 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.