# 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. Group: Number & logic URL: https://digiwleea.wleeaf.dev/learn/twos-complement/ [Binary](https://digiwleea.wleeaf.dev/learn/binary/) shows how to write whole, non-negative numbers as patterns of `0`s and `1`s. 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](https://digiwleea.wleeaf.dev/tools/twos-complement/), or see the trick interactively (the top bit worth -128) in the [negative numbers walkthrough](https://digiwleea.wleeaf.dev/tools/negative-numbers/). > **TIP:** 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. > **KEY:** 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](https://digiwleea.wleeaf.dev/learn/adder8/) and [ALU](https://digiwleea.wleeaf.dev/learn/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 | _The two complements in decimal and in binary. The diminished-radix complement (9's, one's) subtracts each digit from the largest digit (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._ > **TIP:** 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. **Q (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? **A:** 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 | _The same 4-bit patterns read as plain unsigned (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](https://digiwleea.wleeaf.dev/learn/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 + (NOT 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. _Circuit diagram: An 8-bit adder/subtractor (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 `0`s (**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 `1`s just extend the negative weight leftward, and it works out to the same number. Pad a negative with `0`s instead and you would turn `-5` into a large positive value. > **WARN:** **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 `0`s; and remember negating is invert **and add one**, not just invert (that is one's complement, with its two zeros). **Q (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. **A:** 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`.) > **KEY:** Two's complement is the arithmetic the rest of the machine is built on. It lets one [adder](https://digiwleea.wleeaf.dev/learn/adder8/) both add and [subtract](https://digiwleea.wleeaf.dev/learn/subtract/), it defines what the [overflow](https://digiwleea.wleeaf.dev/learn/overflow/) flag is detecting, and it is how the [ALU](https://digiwleea.wleeaf.dev/learn/alu/) does signed math. Next, [boolean algebra](https://digiwleea.wleeaf.dev/learn/boolean-algebra/) gives you the rules for manipulating the `0`s and `1`s themselves, the tool you use to design the gates that make all of this happen. ### FAQ **Q:** What is two's complement? **A:** 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. **Q:** How do you find the two's complement of a binary number? **A:** 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. **Q:** Why does two's complement have only one zero? **A:** 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. **Q:** What is the range of an 8-bit two's complement number? **A:** `-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. **Q:** Why does subtraction work as addition in two's complement? **A:** 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. **Q:** What are 9's complement and 10's complement? **A:** 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`). **Q:** How do you subtract using 10's complement? **A:** 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.