Two's complement
How a computer writes a negative number using nothing but bits, and why that particular way lets one adder do subtraction for free. Every table here is generated and checked, so the arithmetic is right by construction.
What it is
A register holds a fixed number of bits and nothing else: no minus sign. To represent negative numbers, some patterns have to be read as negative. Two's complement does it with one rule: the top bit is worth −2n−1 instead of +2n−1. Every other bit keeps its usual weight. In four bits the weights are −8, 4, 2, 1, so 1011 is −8 + 2 + 1 = −5, and 0101 is plain 5.
The patterns with a 0 on top are the non-negative numbers, exactly as in unsigned binary. The patterns with a 1 on top are the negatives, counting up from the most negative. The whole table for four bits, with the two other signed codes it beat, is below.
Every 4-bit pattern, four ways
| Bits | Unsigned | Sign-magnitude | One's complement | Two's complement |
|---|---|---|---|---|
| 0000 | 0 | 0 | 0 | 0 |
| 0001 | 1 | 1 | 1 | 1 |
| 0010 | 2 | 2 | 2 | 2 |
| 0011 | 3 | 3 | 3 | 3 |
| 0100 | 4 | 4 | 4 | 4 |
| 0101 | 5 | 5 | 5 | 5 |
| 0110 | 6 | 6 | 6 | 6 |
| 0111 | 7 | 7 | 7 | 7 |
| 1000 | 8 | 0 | −7 | −8 |
| 1001 | 9 | −1 | −6 | −7 |
| 1010 | 10 | −2 | −5 | −6 |
| 1011 | 11 | −3 | −4 | −5 |
| 1100 | 12 | −4 | −3 | −4 |
| 1101 | 13 | −5 | −2 | −3 |
| 1110 | 14 | −6 | −1 | −2 |
| 1111 | 15 | −7 | 0 | −1 |
Sign-magnitude uses the top bit as a plain sign and the rest as the size, the way we write numbers on paper. One's complement makes a negative by inverting every bit of the positive. Both have a second zero, marked above, and both need separate logic to add numbers of different sign. Two's complement is one's complement with 1 added to every negative, which removes the duplicate zero, reaches one further negative, and, the real reason it won, adds with an ordinary adder.
How to negate: invert and add 1
To find the pattern for a negative number, write its magnitude in binary at the full width, flip every bit, and add 1. The same two steps go the other way too: inverting and adding 1 negates any number, so a negative pattern put through them comes out as its positive magnitude. Type any number in range, positive or negative, and the steps follow it.
The shortcut. Starting from the right, copy the bits up to and including the first 1, then invert everything to its left. The highlighted bits above are the copied ones; they come out the same because inverting turns the trailing 10…0 into 01…1, and adding 1 turns it straight back.
The binary converter shows the same number in every base at widths from 4 to 32 bits.
Why it works: arithmetic modulo 2n
An n-bit adder throws away any carry out of the top bit, so it is really adding modulo 2n. In that arithmetic, adding 2n − x is the same as subtracting x, because the 2n falls off the end. The two's complement of x is exactly 2n − x: inverting every bit gives (2n − 1) − x, and adding 1 completes it. So the pattern for −x is the number that, added to x, wraps round to zero, which is what a negative number ought to be. Nothing about the adder has to know the sign; the reader decides.
Adding and subtracting
Add the patterns as if they were unsigned, discard the carry out of the top bit, and read the result as two's complement. Subtraction is addition of the negated number: invert the second operand and put a 1 on the carry in, which is the "add 1" of the negation for free. Each column below is a full adder doing exactly that.
| carry | 1 | 1 | 0 | 1 | 0 |
|---|---|---|---|---|---|
| 5 | 0 | 1 | 0 | 1 | |
| −3 | + | 1 | 1 | 0 | 1 |
| 2 | 1 | 0 | 0 | 1 | 0 |
| carry | 0 | 0 | 1 | 0 | 0 |
|---|---|---|---|---|---|
| −6 | 1 | 0 | 1 | 0 | |
| 3 | + | 0 | 0 | 1 | 1 |
| −3 | 0 | 1 | 1 | 0 | 1 |
| carry | 1 | 1 | 0 | 0 | 0 |
|---|---|---|---|---|---|
| −4 | 1 | 1 | 0 | 0 | |
| −2 | + | 1 | 1 | 1 | 0 |
| −6 | 1 | 1 | 0 | 1 | 0 |
| carry | 0 | 0 | 1 | 1 | 1 |
|---|---|---|---|---|---|
| 3 | 0 | 0 | 1 | 1 | |
| 5 | 0 | 1 | 0 | 1 | |
| inverted | + | 1 | 0 | 1 | 0 |
| −2 | 0 | 1 | 1 | 1 | 0 |
The dimmed bit on the far left of each result is the carry out of the top column, which is discarded. In the subtraction the crossed-out row is the number being subtracted, and the row beneath it is what actually enters the adder: the carry in of 1 on the right supplies the +1 of the negation.
This is precisely what a ripple carry adder with an inverting row in front of it does, and why a processor needs no separate subtractor. The full subtractor is the alternative: a borrow chain instead of a carry chain.
Overflow
Four bits hold −8 to 7. Add two numbers whose true sum lies outside that and the adder still produces a pattern, it is just the wrong one: the sum wraps round. The tell is the sign. Two positives can never legitimately add to a negative, nor two negatives to a positive, so a result with the wrong sign means overflow. Adding numbers of mixed sign can never overflow, because the sum lies between them. In hardware the equivalent test is that the carry into the top bit differs from the carry out of it.
| Sum | Bits | Reads as | Carry in to top | Carry out | Overflow? |
|---|---|---|---|---|---|
| 7 + 1 = 8 | 1000 | −8 | 1 | 0 | yes: wrong sign |
| (−8) + (−1) = −9 | 0111 | 7 | 0 | 1 | yes: wrong sign |
| 5 + (−3) = 2 | 0010 | 2 | 1 | 1 | no |
| (−3) + (−4) = −7 | 1001 | −7 | 1 | 1 | no |
The carry out by itself says nothing about signed overflow: the last two rows have a carry out and are fine, the first has none and is wrong, and the second has one and is wrong too. It is the unsigned overflow flag, and processors keep both: a carry flag for unsigned arithmetic and an overflow flag for signed, set from the same adder on every addition.
Ranges
| Width | Unsigned | Two's complement |
|---|---|---|
| 4 bits | 0 to 15 | −8 to 7 |
| 8 bits | 0 to 255 | −128 to 127 |
| 16 bits | 0 to 65,535 | −32,768 to 32,767 |
| 32 bits | 0 to 4,294,967,295 | −2,147,483,648 to 2,147,483,647 |
There is one more negative than positive number at every width, because zero uses up one of the patterns with a 0 on top. The most negative number, −2n−1, is the one value whose negation does not fit: invert and add 1 and you get the same pattern back, with the overflow flag set.
Sign extension
To widen a two's complement number, copy its top bit into every new position. The value does not change: for a positive number the new bits are zeros, and for a negative one the new top bit, the copies, and the old top bit, now positive, add up to exactly the weight the old top bit had: −128 + 64 + 32 + 16 + 8 = −8.
Padding with zeros instead, as for an unsigned number, would turn −5 into 11. Most processors have separate load instructions for the two cases for exactly this reason.
See it in a circuit
The calculator example in the simulator is a 4-bit adder; feed it a number and the two's complement of another, and it subtracts, although its display reads the answer as unsigned, so 3 − 5, entered as 0011 + 1011, lights up the digit for 14 rather than −2. The ripple carry adder page traces the carries column by column, and the binary converter shows any value in two's complement at 4 to 32 bits.
Questions about two's complement
What is two's complement?
The standard way computers represent negative whole numbers. In an n-bit two's complement number the top bit counts as −2ⁿ⁻¹ instead of +2ⁿ⁻¹, and every other bit keeps its usual value. So in eight bits 1111 1111 is −128 + 127 = −1, and 1000 0000 is −128. The same adder that adds unsigned numbers adds these correctly, which is why the representation won.
How do you convert a number to two's complement?
For a positive number, just write it in binary with enough leading zeros to fill the width. For a negative number, write its magnitude in binary, invert every bit, and add 1. To go back, do the same thing: inverting and adding 1 negates a number in either direction. A quicker version: copy the bits from the right up to and including the first 1, then invert everything to the left of it.
What is the range of an n-bit two's complement number?
From −2ⁿ⁻¹ to 2ⁿ⁻¹ − 1. Eight bits hold −128 to 127, sixteen bits −32,768 to 32,767, and thirty-two bits −2,147,483,648 to 2,147,483,647. There is one more negative number than positive because zero takes one of the non-negative patterns, and there is exactly one zero.
Why do computers use two's complement instead of sign-magnitude?
Because subtraction becomes addition. With two's complement, a − b is a + (−b), and negating b is a row of inverters and a carry in, so one adder does both jobs with no special cases for signs. Sign-magnitude and one's complement both need extra logic to handle signs and both have two representations of zero, which every comparison would then have to allow for.
How do you detect overflow in two's complement addition?
When adding, overflow can only happen when both operands have the same sign, and it shows up as a result with the opposite sign: two positives adding to a negative, or two negatives adding to a positive. In hardware the test is that the carry into the top bit differs from the carry out of it. The carry out on its own means nothing for signed numbers; it is only the unsigned overflow flag.
What is sign extension?
Widening a two's complement number without changing its value: copy the sign bit into all the new bits on the left. −5 in four bits is 1011; in eight bits it is 1111 1011. A positive number gets zeros, as usual. Most processors do this when they load a byte into a wider register as a signed value.
Why is −128 special in eight bits?
It is the one number whose negation does not fit. Inverting 1000 0000 gives 0111 1111, adding 1 gives 1000 0000 again, so negating −128 gives −128, and the overflow flag is set. The asymmetry exists because there is one zero and an even number of patterns, so the negatives outnumber the positives by one.