2's complement

All modern computers use 2‘s complement for integer representation.

This encoding gives us only a single representation for zero, and binary addition is much easier than with Signed magnitude because we can just add sequences.

The downside is that we can represent one more negative number than positive (because zero takes up one “spot” on the positive side).

Intuition

the computer only needs to be able to add binary sequences. it does not know or need to care what the two patterns it’s adding actually represent.

so, we should set things up so that when the binary sequences are added, the resulting bit sequence also represents the correct resulting sum.

positive

the specification for positive integers remains the same as 1’s complement. if we have $k$ bits, we use half of the $2^k$ possible numbers to represent values from $0$ to $2^{k-1}-1$.

$0$ takes up one spot, so the value of $2^{k-1}$ can’t be represented.

negative

to get the negative equivalent of the same number, we first flip the bits and then add a 1 to the bit sequence. note that we’re not adding to the representation of the value, just the literal binary.

…and back

and actually, switching between the positive and negative counterpart follows the same procedure.

1. flip all the bits.
2. add 1 to the sequence.

really nice properties

we can repeatedly add 1 to the bit sequences to also get the next integer representation.

Example

if we have a 5-bit system, we can move from $-16=10000$ to $-1=11111$, cross the line over to $0=00000$, and reach $15=01111$ by continually adding 1.

when adding the binary sequences of, let’s say $13=01101$ and $-13=10011$, the resulting bit sequence represents $0=00000$. adding complements cancels out even in binary!

Note

notice that adding $01101$ and $10011$ technically produces $100000$, a 6-bit number. however, in 2‘s complement we can always ignore the carry bit.

Subtraction

As an extension of how easy addition is, subtraction becomes trivial well. Every $a-b$ can be rewritten as $a+(-b)$, and we know how to negate $b$, so to the ALU every subtraction becomes another addition operation.

Integer overflow

2‘s complement also enables easy hardware logic for checking overflow. This occurs when the sign of the number suddenly changes.

• When adding two positive numbers produces negative sum
• When adding two negative numbers produces positive sum

In the ALU, this is detected when $c_{in}\ne c_{out}$ in the most significant bit of the adder.

precision extension

integer precision is determined by the number of bits used in representation. most computers today support 32-bit integers or 64-bit integers.

we extend precision here by extending the sign bit to the left. that is, we fill in the remaining bits with either 0 or 1. we will be told what integer representation is used for the given bit string.

in the same way that leading zeroes does not affect the value of positive numbers, leading ones does not affect the value of negative numbers.