Two’s complement and signed numbers

A byte holds 8 bits, which gives 256 patterns. Read as an unsigned number, they mean 0 to 255. But programs need negative numbers too, and there is no minus sign in memory: some of the 256 patterns have to be given negative meanings. There are several ways to choose which ones. This chapter compares the four that have been used in real machines, and explains why every modern CPU uses the same one, two's complement.

All the examples use 8 bits. Everything works the same for 16, 32 or 64.

Sign-magnitude

The obvious idea is the one we use on paper: keep one bit for the sign (0 for +, 1 for −) and the remaining 7 bits for the absolute value. This is sign-magnitude.

+6 = 0000 0110
−6 = 1000 0110

It's easy to read, but it has two problems. First, there are two zeros: 0000 0000 (+0) and 1000 0000 (−0), which a comparison has to treat as equal. Second, arithmetic is awkward: to add two numbers, the hardware must first compare their signs, then either add or subtract the magnitudes, and in the second case figure out which magnitude is larger. Plain binary addition of the bit patterns gives nonsense: 0000 0110 + 1000 0110 is 1000 1100, which is −12, not 0.

Sign-magnitude isn't dead: floating-point numbers use it, with a separate sign bit, as the floating-point chapter shows.

One's complement

One's complement negates a number by inverting every bit:

+6 = 0000 0110
−6 = 1111 1001

Addition works better: you can add the patterns directly, as long as a carry out of the top bit is added back in at the bottom (the end-around carry). But there are still two zeros: 0000 0000 and 1111 1111. Machines like the CDC 6600 and the UNIVAC 1100 series used one's complement. One's complement is now obsolete in CPUs; its main survivor today is the Internet checksum in IPv4, TCP and UDP headers, which is a one's complement sum of 16-bit words.

Excess-k (biased) notation

Excess-k stores a value v as the unsigned number v + k. With 8 bits and k = 128, −128 is stored as 0 (0000 0000), 0 as 128 (1000 0000), and +127 as 255 (1111 1111). So −6 is stored as 122:

−6 + 128 = 122 = 0111 1010

Its advantage is that the order of the bit patterns matches the order of the values: comparing two excess-k numbers is just an unsigned comparison. That's why IEEE 754 stores floating-point exponents this way, with a bias of 127 for float and 1023 for double. For 8 bits, excess-128 turns out to be two's complement with the top bit flipped.

Two's complement

Think of a car's odometer with three decimal wheels. Starting at 000 and rolling backward one step gives 999. So in a world of 3-digit numbers, 999 behaves exactly like −1: add 1 to it and you get 000, with the carry falling off the end. Two's complement uses the same idea in binary. In n bits, the negative number −x is stored as the unsigned number 2ⁿ − x:

−1 = 256 − 1 = 255 = 1111 1111
−6 = 256 − 6 = 250 = 1111 1010

There is a quicker way to compute it by hand: invert all the bits, then add 1.

+6            0000 0110
invert        1111 1001
add 1         1111 1010   = −6

Another way to read a two's complement number: the top bit has a negative weight. In 8 bits, the bits are worth −128, 64, 32, 16, 8, 4, 2, 1. 1111 1010 is −128 + 64 + 32 + 16 + 8 + 2 = −6. So the top bit also tells you the sign: 1 means negative. That's why it's still called the sign bit, even though it isn't a separate sign.

The whole 3-bit number wheel shows the structure:

There is one zero, and the range is asymmetric: n bits hold −2ⁿ⁻¹ to 2ⁿ⁻¹ − 1. With 2ⁿ patterns (an even number) and one zero, the positives and negatives can't be balanced; two's complement gives the extra pattern to the negatives.

The odd one out, the minimum, has no positive counterpart. Negating −128 (1000 0000) by inverting and adding 1 gives 0111 1111 + 1 = 1000 0000: −128 again.

The four systems side by side

Why two's complement won

The decisive property: adding the bit patterns as unsigned numbers gives the right two's complement answer, as long as you drop the carry out of the top bit. −6 + 10:

  1111 1010    (−6, or 250 unsigned)
+ 0000 1010    (10)
= 1 0000 0100  → drop the carry → 0000 0100 = 4

As unsigned numbers this was 250 + 10 = 260, and 260 − 256 = 4. As signed numbers it was −6 + 10 = 4. Both readings are right at the same time. So a CPU needs only one adder and one add instruction for signed and unsigned numbers, and subtraction is just adding the negation: a − b = a + (inverted b) + 1, which an adder does by inverting one input and setting its carry-in to 1. The adders chapter builds that circuit.

Every mainstream CPU today uses two's complement, and the C23 standard finally made it the only representation C allows. Since the bits alone don't say whether a value is signed, the instruction does: x86 has separate signed and unsigned versions of comparisons, widening, right shifts, multiplication and division. The data types chapter lists the pairs.

Sign extension

To widen a two's complement number (from 8 to 16 bits, say), copy the sign bit into all the new positions. This is sign extension:

−5 in 8 bits:              1111 1011
−5 in 16 bits:   1111 1111 1111 1011
+5 in 8 bits:              0000 0101
+5 in 16 bits:   0000 0000 0000 0101

It works because the copies add up to the same negative weight: in 16 bits, bits 15 down to 7 of −5 are worth −32,768 + 16,384 + … + 256 + 128 = −128, exactly what the sign bit alone was worth in 8 bits. Unsigned numbers are widened with zeros instead (zero extension). Mixing the two up is a classic bug: the byte 0xFB becomes 251 or −5 depending on which extension the compiler picks, which depends on the declared type.

Overflow and how to detect it

With a fixed number of bits, some results don't fit. For unsigned numbers, the result is wrong when there is a carry out of the top bit: 200 + 100 = 300 doesn't fit in a byte. For signed numbers the rule is different, and there are three equivalent ways to state it:

1. Signs: adding two numbers of the same sign gives a result of the opposite sign. (Adding numbers of opposite signs can never overflow.)
2. Carries: the carry into the sign bit differs from the carry out of it.
3. Range: the true result is outside −128 to 127.

The CPU computes both conditions on every addition and subtraction and records them as two flags: CF, the carry flag (unsigned overflow), and OF, the overflow flag (signed overflow). A few cases, checked bit by bit:

The simulator shows the same flags. Step through the program and watch CF and OF after each instruction:

neg al turns 5 into 0xFB, shown as 251 unsigned, which is −5. 100 + 50 leaves 0x96 (−106 signed) with OF = 1 and CF = 0: fine as unsigned (150), wrong as signed. −100 + −50 leaves 106 with both flags set: wrong both ways. −1 + 1 gives 0 with CF = 1 but OF = 0: as unsigned, 255 + 1 overflowed; as signed, the answer is right. 5 − 7 gives 0xFE, −2, with CF = 1: after a subtraction, x86's carry flag means borrow: the unsigned result would have been negative. (ARM does the opposite: after a subtraction, its carry flag is 1 when there was no borrow.) The last instruction negates −128 and gets −128 back, with OF = 1.

Which flag matters is the program's choice: jo and the signed comparisons (jl, jg) look at OF; jc and the unsigned ones (jb, ja) look at CF. The flags chapter shows how compilers use them.

Overflow in real programs

Hardware wraps around silently; languages differ on what that means.

• In C and C++, signed overflow is undefined behavior: the compiler may assume it never happens, and optimize accordingly. Unsigned arithmetic, by contrast, is defined to wrap modulo 2ⁿ.
• Rust panics on overflow in debug builds and wraps in release builds; Java and Go always wrap.
• The asymmetric minimum causes its own surprises. abs(INT_MIN) returns INT_MIN, still negative. And INT_MIN / -1, whose true result 2,147,483,648 doesn't fit, behaves differently by architecture: x86's idiv raises a divide-error exception (Linux turns it into SIGFPE and the program dies), while ARM64's sdiv quietly returns INT_MIN. Compiled with gcc on ARM64 Linux, a test program printed INT_MIN / -1 = -2147483648 and carried on; the same division in the simulator stops with a #DE divide error.

Takeaways

• Sign-magnitude and one's complement have two zeros and need special hardware for signed arithmetic. Excess-k stores v + k and keeps values in order, which is why float exponents use it.
• Two's complement stores −x as 2ⁿ − x: invert the bits and add 1. The top bit has weight −2ⁿ⁻¹. Range: −2ⁿ⁻¹ to 2ⁿ⁻¹ − 1, one zero, and one extra negative number that is its own negation.
• Its killer property: the same adder works for signed and unsigned, and subtraction is addition of the negation. Every modern CPU uses it; C23 requires it.
• Sign extension copies the sign bit when widening; zero extension is for unsigned values.
• Unsigned overflow = carry out of the top bit (CF). Signed overflow = carry into the sign bit ≠ carry out, or equivalently two same-sign operands giving an opposite-sign result (OF).
• Languages treat overflow differently: undefined in C for signed types, a panic in debug Rust, a wrap in Java. INT_MIN / -1 traps on x86 and returns INT_MIN on ARM64.