Two's complement
How hardware stores negative numbers
Two's complement is the standard way computers store signed integers: the most significant bit carries a negative weight of -2^(n-1), so to negate a number you invert all its bits and add one, and a single adder then handles both addition and subtraction.
Builds onBinary numbers
Binary shows how to write whole, non-negative numbers as patterns of
0s and 1s. But a computer only has bits, no minus sign, so how does it store -5? You have to choose a code: agree in advance how a pattern of bits stands for a negative value. Three codes were tried over the years, and the last one, two's complement, won so completely that every modern CPU uses it. The reason is simple and worth the whole lesson: in two's complement, subtraction is just addition, so the same adder hardware does both. Convert signed decimals to and from two's complement at any bit width with the two's complement calculator, or see the trick interactively (the top bit worth -128) in the negative numbers walkthrough.Think of a 12-hour clock. Going back 3 hours from 12 lands on 9, and so does going forward 9 hours:
-3 and +9 are the same move because the clock wraps around at 12. Fixed-width binary wraps the same way (at 2^n instead of 12), and that wrap-around is exactly what lets one operation, addition, also do subtraction. Two's complement is the code that lines the negatives up with that wrap.First tries: sign-magnitude and one's complement
The obvious idea is sign-magnitude: steal the top bit as a sign flag (
0 = positive, 1 = negative) and read the rest as the size. So in 4 bits 0101 is +5 and 1101 is -5. It is easy to read, but it has two ugly problems. First, there are two zeros: 0000 is +0 and 1000 is -0, the same value with two patterns. Second, adding is awkward: +5 plus -5 does not naturally give zero, because the hardware has to compare signs and magnitudes and decide whether to add or subtract. A plain binary adder gets the wrong answer.One's complement improves on it: a negative number is the bitwise inversion of its positive (flip every bit). So
+5 is 0101 and -5 is 1010. Addition almost works with a normal adder, but you must take any carry that falls off the top and add it back in at the bottom (the end-around carry), an extra step. And it *still* has two zeros: 0000 and 1111 both mean zero. Close, but not clean.Two's complement: invert and add one
Two's complement takes one's complement and fixes both flaws with a single tweak. To get the negative of a number, invert every bit and then add 1:
-5 in 4 bits: 5 = 0101
→ invert: 1010
→ add 1: 1011 = -5
Now
0000 + 1 = 0001 working upward, and there is exactly one zero: inverting 0000 gives 1111, and adding 1 wraps it back to 0000, so negative zero collapses into positive zero. One pattern, one value. There is also a quick shortcut for doing it in your head: copy the bits from the right up to and including the first 1, then invert everything to the left of it. For 0101 the rightmost 1 is the low bit, so copy that 1 and invert the rest: 1011. Same answer, no carry to track.Why this matters: two's complement is not just one valid code among several, it is the code that makes a CPU's arithmetic cheap. Because negating is invert-and-add-one and the bits wrap at
2^n, one ordinary binary adder adds and subtracts both signed and unsigned numbers with no special cases. Sign-magnitude and one's complement each needed extra hardware; two's complement needs none. That is why your adder and ALU will use it without a second thought.Where invert-and-add-one comes from: complement arithmetic
Invert-and-add-one is not something invented for computers. It is the base-2 case of a much older idea, complement arithmetic, used for centuries to turn subtraction into addition in any number base. Every base
b (radix is just another word for base) has two complements of a number. The radix complement subtracts the number from b raised to its digit count. The diminished-radix complement subtracts it from the largest value those digits can hold, which is one less than that power. In the decimal you grew up with, b = 10, so these are the 10's complement and the 9's complement.Take
42 as a two-digit number. Its 9's complement subtracts each digit from 9, the largest decimal digit: 9 - 4 = 5 and 9 - 2 = 7, giving 57. Its 10's complement is one more, 57 + 1 = 58, which is also 100 - 42. Subtracting each digit from 9 is the whole convenience: it never needs a borrow, and the final +1 is trivial.9's complement of 42: 99 - 42 = 57 10's complement of 42: 100 - 42 = 58 = 57 + 1
Now watch subtraction turn into addition. To compute
67 - 42, add 67 to the 10's complement of 42 instead of subtracting:67 - 42
→ 67 + 58 = 125
→ drop the carry (the leading 1)
→ 25
You added
67 + 58 = 125, then threw away the carry that spilled past two digits. That leftmost 1 is worth 100, and adding the 10's complement had quietly added that same 100 (because 58 = 100 - 42), so discarding it cancels the extra and leaves the true answer, 25. One addition and one dropped digit did the subtraction. This clean version (just drop the carry) works whenever the answer is not negative, as here where 67 > 42.The 9's complement reaches the same answer with one extra step. Add
67 to the 9's complement 57: 67 + 57 = 124. This time you do not throw the carry away, you wrap it around: remove the leading 1 and add it back into the ones place, 24 + 1 = 25. That feedback is called the end-around carry, and it appears because the 9's complement is one short of the 10's complement, so you hand that missing 1 back at the end. It is the very same end-around carry you saw with one's complement earlier in this lesson.Binary is just base 2, and both complements have a base-2 form you have already been using. The diminished-radix complement subtracts each digit from the largest digit; in base 2 the largest digit is
1, and 1 - 0 = 1, 1 - 1 = 0, so subtracting from 1 is exactly inverting the bit. That is one's complement, and like the 9's complement it carries around at the end. The radix complement adds one more: invert every bit, then add 1. That is two's complement, and like the 10's complement you simply drop the carry that falls off the top. So the mysterious +1 is not special at all: it is the same step that promotes a 9's complement to a 10's complement, performed in base 2.| base | diminished-radix complement | radix complement |
|---|---|---|
| 10 (decimal) | 9's complement | 10's complement |
| 2 (binary) | one's complement | two's complement |
9, or in binary just 1, so it becomes plain bit inversion) and needs an end-around carry. The radix complement (10's, two's) adds 1 more and lets you discard the carry-out instead. Two's complement is nothing but the radix complement of base 2, which is exactly why a single adder can also subtract.The same rule reaches past whole numbers. For a fixed-point value you pin a binary point at an agreed position and keep the usual weights, with the top bit still carrying its negative weight. Negating does not change: invert every bit and add a
1 in the least significant position. For example, with two fractional bits 01.10 is +1.5; invert to 10.01 and add the low 1 to get 10.10, which reads as -2 + 0.5 = -1.5. The point never moves, only the bits flip.Try it
Compute
53 - 61 with two-digit decimal 10's complement: add the 10's complement of 61, then look at the carry. What does the result tell you, and how does that mirror two's complement in binary?Answer
The 10's complement of
61 is 100 - 61 = 39. Add: 53 + 39 = 92. This time there is no carry out of the two digits, and that missing carry is the signal that the real answer is negative. The 92 you are holding is the 10's complement of the magnitude (100 - 92 = 8), so the answer is -8 (and indeed 53 - 61 = -8). Binary two's complement behaves identically: subtract a larger number and you get no carry-out and a pattern whose top bit is 1, which you read back as negative. The negative result is already sitting there in complement form, no extra conversion needed.The real trick: the top bit has a negative weight
Here is the clean way to understand two's complement, no inverting required. In an unsigned 4-bit number the bits have weights
8, 4, 2, 1. In two's complement the most significant bit's weight is made negative: -8, 4, 2, 1. Every other bit keeps its normal positive weight. To read a signed value, just add up the weights of the bits that are 1:1011 = (-8) + 0 + 2 + 1 = -5 0111 = 0 + 4 + 2 + 1 = +7
For
n bits the top bit's weight is -2^(n-1). That single sign-weighted bit is the whole representation: a pattern is negative exactly when its top bit is 1 (because only then is the big negative weight in play), and reading any value is just a weighted sum. The same table read two ways makes it concrete:| bits | unsigned | signed |
|---|---|---|
| 0000 | 0 | 0 |
| 0001 | 1 | 1 |
| 0011 | 3 | 3 |
| 0111 | 7 | 7 |
| 1000 | 8 | -8 |
| 1001 | 9 | -7 |
| 1011 | 11 | -5 |
| 1100 | 12 | -4 |
| 1110 | 14 | -2 |
| 1111 | 15 | -1 |
0..15) and as two's-complement signed (-8..+7). The low half (top bit 0) reads the same both ways; the top half (top bit 1) is where the -8 weight kicks in, so 1111 is 15 unsigned but -1 signed (-8 + 4 + 2 + 1).The range is lopsided, and one number cannot be negated
Because one bit is spent on the negative weight, the range is not symmetric. With
n bits two's complement covers -2^(n-1) up to 2^(n-1) - 1: there is one more negative number than positive, because zero takes up a slot on the positive side. In 8 bits that is -128 to +127, not -128 to +128.n bits: -2^(n-1) to 2^(n-1) - 1 8 bits: -128 to +127
That asymmetry has a famous consequence: the most negative number has no positive partner, so negating it cannot work. Try to negate
-128 in 8 bits with invert-and-add-one:-128 = 1000 0000
→ invert: 0111 1111
→ add 1: 1000 0000 = -128 again
Negating
-128 gives -128 back, because +128 does not fit in signed 8-bit. The same thing happens with the most negative value at any width. It is not a bug in the procedure, it is the range running out of room, and real CPUs simply flag it as an overflow.Subtraction is just addition
This is the payoff. To compute
A - B, add A to the negative of B. And the negative of B is invert-and-add-one, so:A - B = A + (¬B) + 1
An ordinary adder already sums two numbers; feed it
A and the inverted B, and slip the +1 in through the adder's carry-in. No subtractor circuit is needed. The figure below is the 8-bit adder/subtractor you will build later: with SUB = 1 it inverts B and sets carry-in to 1, so it subtracts; with SUB = 0 it adds. Hold every A input at 0 and set SUB = 1 and it simply negates B (0 - B). Try B = 1000 0000 (-128) and watch the output come back as -128, the most-negative special case in action.ADDSUB8). Open it in the lab: with SUB = 0 it computes A + B; with SUB = 1 it computes A - B by feeding the adder NOT B and a carry-in of 1 (two's complement). Set all A inputs to 0 and SUB = 1 to negate B. The very same adder serves signed and unsigned numbers.Widening a number: sign extension
When you copy an 8-bit value into a 16-bit slot, you must fill the new high bits without changing the value. For an unsigned number you pad with
0s (zero extension): 0000 0101 becomes 0000 0000 0000 0101, still 5. For a signed two's-complement number you must copy the sign bit into every new bit (sign extension), so a negative stays negative:+5 = 0000 0101
→ 0000 0000 0000 0101 (pad with 0) -5 = 1111 1011
→ 1111 1111 1111 1011 (pad with 1)
Sign extension keeps the value because copying the sign bit preserves the weighted sum: the extra
1s just extend the negative weight leftward, and it works out to the same number. Pad a negative with 0s instead and you would turn -5 into a large positive value.Common mistakes. A bit pattern has no sign by itself:
1111 1011 is 251 read as unsigned and -5 read as signed, and only *you* (or the instruction the CPU runs) decide which. So do not say a pattern "is negative", say it "is negative *when read as signed*". Three more traps: the range is lopsided (-128 to +127, not -128 to +128), so the most negative value cannot be negated; widen a signed number by sign-extending (copy the top bit), never by padding with 0s; and remember negating is invert and add one, not just invert (that is one's complement, with its two zeros).Try it
In 8-bit two's complement, what bit pattern is
-1? Work it out with invert-and-add-one starting from +1, then check it with the negative-weight method.Answer
Start from
+1 = 0000 0001. Invert: 1111 1110. Add 1: 1111 1111. So -1 = 1111 1111, all ones. Check with weights: 1111 1111 = -128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = -128 + 127 = -1. (It makes sense that -1 is all ones: add 1 to it and every bit carries, wrapping to 0000 0000, which is 0.)Two's complement is the arithmetic the rest of the machine is built on. It lets one adder both add and subtract, it defines what the overflow flag is detecting, and it is how the ALU does signed math. Next, boolean algebra gives you the rules for manipulating the
0s and 1s themselves, the tool you use to design the gates that make all of this happen.Frequently asked
What is two's complement?
Two's complement is the standard code for signed integers in hardware: the most significant bit is given a negative weight of
-2^(n-1) while every other bit keeps its normal positive weight. To negate a number you invert all its bits and add 1. Its big advantage is that one ordinary binary adder then handles both addition and subtraction, with a single representation for zero.How do you find the two's complement of a binary number?
Invert every bit (
0 becomes 1, 1 becomes 0) and then add 1. For example +5 = 0101 inverts to 1010, and adding 1 gives 1011 = -5. A quick shortcut: copy the bits from the right up to and including the first 1, then invert everything to its left.Why does two's complement have only one zero?
Negating
0 should give 0. Inverting 0000 gives 1111, and adding 1 wraps it back to 0000, so the "negative zero" pattern collapses into the single 0000. Sign-magnitude and one's complement both have two zeros (a +0 and a -0); two's complement has exactly one, which is part of why it won.What is the range of an 8-bit two's complement number?
-128 to +127. With n bits the range is -2^(n-1) to 2^(n-1) - 1, which is lopsided (one extra negative) because zero takes a slot on the positive side. A consequence is that the most negative value, -128, has no positive partner, so negating it overflows and gives -128 back.Why does subtraction work as addition in two's complement?
Because
A - B = A + (-B) and -B is just NOT B + 1. So A - B = A + (NOT B) + 1: feed an ordinary adder A and the inverted B, and supply the +1 through the carry-in. No separate subtractor is needed, which is exactly why CPUs use one adder for both operations.What are 9's complement and 10's complement?
They are the two complements of a decimal number. The 9's complement subtracts each digit from
9 (so 42 becomes 57); the 10's complement adds 1 more, or equivalently subtracts the number from the next power of ten (100 - 42 = 58). Both let you replace subtraction with addition in base 10. They are the general diminished-radix and radix complements applied to base 10, and in base 2 the very same ideas are one's complement (invert every bit) and two's complement (invert and add 1).How do you subtract using 10's complement?
Add the 10's complement of the number you are subtracting, then discard the carry that falls off the left. For
67 - 42: the 10's complement of 42 is 58, and 67 + 58 = 125, so dropping the leading 1 leaves 25. With the 9's complement instead you add that dropped carry back into the units (the end-around carry): 67 + 57 = 124, then 24 + 1 = 25. Binary two's-complement subtraction works exactly the same way, which is why one adder can both add and subtract.Every lesson here builds toward one thing: a working CPU, from the transistor up.
Open the free lab →