Two’s Complement
Two’s Complement¶
A computers physical limitations create overflow during addition. Overflow can actually be very useful. We can use it to create subtraction. Instead of building subtraction into a computer processor, we can use overflow and addition to simulate subtraction.
We have already seen that the largest number an 8-bit computer can store is \(255_{10}\). If we added two numbers together and their total was \(256_{10}\), that would give us \(0_{10}\) with overflow on an 8-bit computer.
How can we use this to create subtract? Let us create \(-17\) as an example.
\( \begin{align} 17+x =& 256 \\ x =& 256-17 \\ x =& 239 \\ \end{align} \)
If we ask an 8-bit computer to determine \(17_{10}+239_{10}\) it will give us \(0_{10}\) with a overflow. If we ignore the overflow, we have \(17_{10}+239_{10}=0_{10}\). What happens if we add \(239_{10}\) to other numbers in 8-bits.
\( \begin{align} 25_{10}+239_{10} =& 8_{10} \\ 30_{10}+239_{10} =& 13_{10} \\ 99_{10}+239_{10} =& 82_{10} \\ \end{align} \)
The value \(239_{10}\) works just like \(-17_{10}\) because of overflow.
Two’s Complement allows us to convert a binary number into a value that will act like a negative.
To convert a binary number to Two’s Complement.
Flip All Bits (1 to 0, 0 to 1)
Add 1 to the Number
For example, we can make \(17\) into \(-17\) using these steps.
Value |
128 |
64 |
32 |
16 |
8 |
4 |
2 |
1 |
|---|---|---|---|---|---|---|---|---|
17 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
Flip Bits |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
-17 (add 1) |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
What binary number did Two’s Complement actually produce? It gives us 1110 1111, which is \(239_{10}\).
Now we just need to complete a normal addition and ignore the overflow to subtract.
For example, \(99_{10}-17_{10} = 82_{10}\) is
\( \begin{align} & 1101 1110 & \text{(Carry)} \\ & 0110 0011 & \text{Value 1)} \\ +& 1110 1111 & \text{(Value 2)} \\ & = & \\ & 0101 0010 & \text{(Result)}\\ \end{align} \)
Subtraction works correctly.
This raises an interesting question. Does 1110 1111 mean \(-17_{10}\) or \(239_{10}\)? That depends on how we use it as programmers. If we are working with only positive numbers, we would consider it \(239_{10}\). When working with negative numbers, we treat numbers starting with a 1 as negative and numbers starting with a 0 as positive. The computer hardware doesn’t know the difference. It is up programmers to tell the computer what type of numbers we are working with.