Two's Complement

Two's complement is the encoding nearly every computer uses for signed integers. In an n-bit word the leftmost column carries a place value of −2ⁿ⁻¹ instead of +2ⁿ⁻¹, so an 8-bit byte spans −128 through 127. To negate a number you invert every bit and add 1; subtraction then becomes ordinary addition.

It did not win because it reads nicely. It won because a machine built to add unsigned numbers already adds signed ones correctly, on the same adder, with no branch anywhere. The obvious alternative — spend one bit on a sign, the rest on a magnitude — is easy for a human to read and forces the hardware to compare signs before every addition or subtraction. Two's complement takes the sign out of the flag business and folds it into the place-value system, where the ordinary rules of base 2 keep doing the work.

The Top Bit Is a Place Value, Not a Sign Flag

Start with what an unsigned byte already means. 10110101 is 128 + 32 + 16 + 4 + 1 = 181: each column carries a fixed weight, and you add up the columns holding a 1. That is the whole of positional notation.

Two's complement changes exactly one weight and nothing else. In an 8-bit word the leftmost column is worth −128, not +128. Column 6 is still 64, column 0 is still 1, and you still just add up the columns holding a 1. So 11111100 is 64 + 32 + 16 + 8 + 4 + (−128) = −4. Every negative number has a 1 in the top column, because that is the only column that can drag the total below zero — but the bit is a place value, not a marker, and treating it as a marker is where most of the confusion starts.

That single change is enough to make negation mechanical. Take any 8-bit pattern x and flip every bit to get ~x. Every column now holds a 1 in exactly one of the two patterns, so x + ~x is 11111111 — which, under the rule above, reads as −1. Rearrange: ~x + 1 = −x. Invert and add 1 is not a trick someone found by trial; it falls straight out of the fact that all-ones means −1.

The payoff arrives at the adder. Column-by-column addition never asks what a pattern means — it adds three bits (one from each operand, one carried in), writes the low bit, and passes the high bit along. Feed it two two's-complement patterns and it produces the correct signed answer when the mathematical sum fits; otherwise the low n bits wrap and signed overflow must be detected. A carry that leaves the top column has no column left to land in, so it is dropped, which is exactly the arithmetic-modulo-2ⁿ behavior the encoding was designed around.

Two's Complement Step by Step

The default run negates x = 4 in an 8-bit word. Three rows stack up, one per stage of the derivation.

1. The word starts empty. Eight columns, weights −128, 64, 32, 16, 8, 4, 2, 1 from left to right. There is no minus key; the sign has to come out of the pattern.
2. Write the magnitude. 4 is a single place value, so |x| = 00000100 in ordinary base 2.
3. Invert every bit. 00000100 becomes 11111011. Each column flips on its own; no column consults its neighbour. This is the one's complement, and on its own it is not the answer.
4. Add 1. 11111011 ends in two 1s, so the 1 does not simply land — it ripples. Bit 0 goes 1 → 0 and passes a carry left, bit 1 does the same, and bit 2 finally has room to absorb it. The result is 11111100. (Negate 5 instead and the ripple never starts, because bit 0 of 11111010 is already 0.)
5. Read the positive weights. Columns 6, 5, 4, 3, and 2 hold a 1: 64 + 32 + 16 + 8 + 4 = 124. Read as an unsigned byte, the whole pattern would be 252 — that is the misreading to have in mind for the next line.
6. Count the top column too. It holds a 1 and it weighs −128, so the total is 124 + (−128) = −4. The pattern was never doing anything exotic; the only surprise was the sign on one weight.
7. Done. −4 is 11111100. Invert and add 1 on that pattern and 4 comes back, so the operation is its own inverse — and because the sign lives in a weight rather than a flag, an adder can now run over these patterns without testing anything.

On the canvas, the row under construction is the bright one and the finished rows dim to context weight, so the beat you are on is always the loudest thing on screen. The place values sit under the columns: the positive ones light up together, then the negative top weight joins to finish the sum.

Why One Adder Is Enough for Signed Arithmetic

Switch to the add variant and the lesson stops being about encoding and starts being about what the encoding buys. It computes a + b with a plain ripple adder — the same loop you would write for unsigned values, with no sign test in it.

With the variant's own default, a = 5 (00000101) and b = −3 (11111101), the sweep runs from bit 0 upward. Bit 0: 1 + 1 + 0 = 2, so write 0 and carry 1. Bit 1: 0 + 0 + 1 = 1, so write 1 and carry 0. Bit 2: 1 + 1 + 0 = 2, write 0, carry 1. Bit 3: 0 + 1 + 1 = 2, write 0, carry 1 — and bits 4 through 6 repeat that same column exactly. Bit 7, the sign column, runs the identical rule: 0 + 1 + 1 = 2, write 0, carry out 1. The result is 00000010 = 2, and 5 + (−3) is indeed 2. Subtraction never happened; addition did.

That leftover carry out of the top column is dropped, because there is no ninth column to hold it. Dropping it is normal bookkeeping, not an error signal — this run discarded a carry and still produced a perfectly correct answer.

Signed overflow is a different test, and confusing the two is the classic bug. Overflow means the true result does not fit in the range, and the rule that detects it is: the carry into the top column differs from the carry out of it. In the run above both were 1, so the answer is trustworthy. Load the Overflow: 127 + 1 preset and the numbers separate: the carry into the top column is 1 and the carry out is 0, they disagree, and the answer wraps from a true sum of 128 to −128. That one comparison is the only thing the encoding costs a designer — the adder itself is unchanged. This model displays the overflow comparison but does not trap. Hardware flags and programming-language checks vary; signed overflow is not universally a silent, defined wrap.

The trace masks every intermediate back to n bits on purpose. Mathematical integers are unbounded and never wrap, so the mask is what stands in for a fixed-width machine word; a fixed-width register retains only those bits. Language semantics still matter: C signed overflow is undefined, and Rust can check overflow and panic instead of returning a wrapped result.

Edge Cases

• The range is asymmetric. An 8-bit word holds −128 through 127, so −128 has no positive twin. Negating the pattern for −128 by invert-and-add-1 returns 10000000, still −128 in this wrapping model. Its mathematical absolute value 128 is not representable in the same signed type; an abs(INT_MIN) call must not be assumed to return a valid positive result.
• Zero has exactly one encoding. 00000000 and nothing else. One's complement and sign-magnitude both carry a second "negative zero" pattern, which every comparison then has to special-case. This is the quiet reason two's complement won.
• Carry out is not overflow. 5 + (−5) produces a carry out of the top column and the answer 0, which is correct. 127 + 1 produces no carry out and the answer −128, which is wrong. The two events are independent.
• Narrow words wrap sooner. In the 4-bit preset the range is −8 through 7, so 7 + 1 already overflows to −8. The rules are identical; only the range moved.
• Right-shifting a negative value is not one operation. An arithmetic shift copies the sign bit inward and preserves the value's sign; a logical shift by a nonzero count feeds in zeros and leaves a nonnegative result. Which one you get depends on the language and the type, not on two's complement itself.

Common Mistakes

• Treating the top bit as a sign flag. Flipping just that bit gives you sign-magnitude, and it produces a second zero. To negate a two's-complement value you invert every bit and add 1.
• Stopping at the one's complement. Skip the + 1 and every negative value except the range floor sits one below where you wanted it: 11111011 reads as −5, not −4. At the floor, ~10000000 is 01111111, the top of the range.
• Detecting overflow with the carry out. Flagging overflow whenever a carry leaves the top column falsely condemns correct answers like 5 + (−5), and it misses 127 + 1 entirely. Compare the carry into the top column with the carry out of it.
• Assuming the wrap is guaranteed. The wrap-around you see here is what the hardware does. In C and C++, signed integer overflow is undefined behavior, and optimizers are allowed to assume it never happens — which is how if (x + 1 < x) gets deleted from a build.
• Mixing signed and unsigned in a comparison. On common platforms, comparing an int against a size_t converts the signed side to an unsigned type, so −1 becomes a large positive value. The exact conversion follows the types' ranks and representable ranges; do not assume the comparison preserves the signed ordering.