# Number Representation

### Two's Complement: More Details

#### Sign extension

Note that in two's complement, non-negative numbers have an implicit infinite number of leading 0's, and negative numbers have an implicit infinite number of leading 1's.

For example,

```        `    0 = 00000000 = 00000000 00000000` ( = 010 )
`00010 = 00000010 = 00000000 00000010` ( = 210 )
`11110 = 11111110 = 11111111 11111110` ( = -210 )
`01101 = 00001101 = 00000000 00001101` ( = 1310 )
`10011 = 11110011 = 11111111 11110011` ( = -1310 )```

#### Proving the relationship between One's Complement and Two's Complement

Prove: -x = x + 1

[In our examples, we will assume that integers are 8 bits long, but the proof applies to binary integers of any length (e.g., 16 bits, 32 bits, 64 bits).]

Let `x` represent the one's complement of `x`.

Note that in two's complement, the definition of `-1` is `11111111` (the result of subtracting `1` from `0`).

Note that `x + x = 11111111 = -1`. This is true because for every `0` in `x`, the corresponding bit in `x` is `1`, yielding a sum bit of `1`, and for every `1` in `x`, the corresponding bit in `x` is `0`, again yielding a sum bit of `1`. For example:

```        `   00001101`   13
` + 11110010`   one's complement of 13
` ----------`
`   11111111````

Since

`   `x + x = -1``
we can add one to both sides and get
`   `x + x + 1 = 0``

Now, by definition,

`   `x + (-x) = 0``
so, substituting `x + (-x)` for 0 in our previous result, we have
`   `x + x + 1 = x + (-x)``
or
`   `x + 1 = (-x)``
or
`   `(-x) = x + 1``

#### Overflow

• Overflow cannot occur when adding numbers of different signs, so we can ignore the extra borrows and carrys in that case.

• Overflow cannot occur when subtracting two numbers with the same sign.

• Overflow occurs when you:
• Add 2 positive numbers and get a negative sum.
• Add 2 negative numbers and get a positive sum.
• Subtract a positive number from a negative number and get a positive difference.
• Subtract a negative number from a positive number and get a negative difference.

• Ignoring overflow:
• In MIPS, `addu`, `subu`, and `addiu` all ignore overflow (unsigned integer calculations); the "sign bit" gives an extra digit's worth of positive numbers we can express.
• C always ignores overflow; catching it is the programmer's responsibility.