How Integers Are Encoded: Two's Complement

Part I · Module 2 · Chapter 2.7 · How Integers Are Encoded: Two's Complement

1. The Gap Left by Chapter 2.4

Chapter 2.4 gave you a complete mechanism for reading a bit pattern: each position is worth twice the one to its right, and you add up the positions that are set. It works perfectly, and it can only ever produce a value of zero or more.

Chapter 2.6 then spent a chapter on signed types, which hold negative values. So a question is outstanding: what does −5 look like in bits?

There is no minus sign to store. There are only bits. Whatever the answer is, it has to be a pattern of ones and zeros that the machine agrees to read as negative — which means the encoding is a convention, and conventions can be chosen well or badly.

Throughout this chapter, patterns are shown 8 bits wide. That is a teaching width, chosen because it fits on a line. It is not a C type — a real int is wider, as Chapter 2.5 established. The mechanism is identical at any width.

2. The Obvious Idea, and Why It Was Not Chosen

The first idea anyone has is to sacrifice one bit as a sign flag: leftmost bit 0 means positive, 1 means negative, and the remaining bits hold the size.

  0000 0101   →  +5
  1000 0101   →  -5   (leftmost bit says "negative")

Readable, obvious, and it creates two problems immediately.

There are two zeros. 0000 0000 is +0 and 1000 0000 is −0. Two patterns for one value, and every comparison for zero has to check both.

Arithmetic stops working. Add 0000 0101 (+5) and 1000 0101 (−5) with ordinary binary addition and you get 1000 1010, which in this scheme reads as −10. The answer should be 0. So the machine would need a separate procedure for adding when signs differ — more hardware, more complexity, and a special case for every operation.

That second problem is the fatal one, and it points straight at what a good encoding would have to do.

3. Deriving the Encoding from What It Must Do

Set aside how negatives "should" look and ask what the encoding has to achieve:

Adding a number to its negative, using ordinary binary addition and nothing special, must give zero.

If that holds, the machine needs one adder and no special cases. So: what pattern, added to 0000 0101, gives zero?

Work it out in two steps. First find something that makes all the bits into ones:

    0000 0101        +5
  + 1111 1010        every bit flipped
  ─────────────
    1111 1111        all ones

Flipping every bit gets you to all-ones, always — that is what flipping means. Now all-ones is one short of rolling over. Add one more:

    1111 1111        all ones
  +         1
  ─────────────
  1 0000 0000        rolls over

In eight bits, that leaves 0000 0000 — zero — with the carry falling off the end.

So the pattern that behaves as −5 is flip every bit, then add one:

    0000 0101        +5
    1111 1010        flip every bit
  +         1        add one
  ─────────────
    1111 1011        this is -5

Check it:

    0000 0101        +5
  + 1111 1011        -5
  ─────────────
  1 0000 0000        zero, carry discarded

It works, with ordinary addition and no special cases. This encoding is called two's complement, and it was not chosen because it is elegant to look at — it was chosen because it makes subtraction free.

4. Reading a Negative Pattern

Going the other way uses the same move. Given a pattern you know is negative — leftmost bit set — flip and add one to find its size:

    1111 1011        the pattern
    0000 0100        flip every bit
  +         1        add one
  ─────────────
    0000 0101        = 5, so the pattern was -5

Two things fall out of the scheme that are worth knowing directly.

The leftmost bit tells you the sign — 1 means negative — but it is not merely a flag. It carries weight, just a negative one. In eight bits its worth is −128 rather than +128, and reading a pattern as "−128 plus the rest" gives the same answer as flip-and-add-one:

  1111 1011   =  -128 + 64 + 32 + 16 + 8 + 0 + 2 + 1  =  -5

There is exactly one zero. 0000 0000 is zero; flipping and adding one gives 0000 0000 back. The two-zeros problem is gone.

5. Why the Range Is Lopsided

Chapter 2.5's table had ranges like −32768 to 32767 on the machine that ran it — one further in the negative direction than the positive. That asymmetry is not a rounding choice. It is forced by §4.

Count the patterns. Eight bits give 256 of them. One is spent on zero. That leaves 255 to split between positives and negatives, and 255 is odd, so the split cannot be even. Two's complement gives the extra one to the negatives:

  0000 0000                zero            (1 pattern)
  0000 0001 … 0111 1111    +1 to +127      (127 patterns)
  1000 0000 … 1111 1111    -128 to -1      (128 patterns)

So an 8-bit signed value runs −128 to +127.

This has a consequence that matters in real code: the most negative value has no positive counterpart. There is no +128 in eight bits, so negating the most negative value cannot produce a representable result. In C, doing so with a signed type is the signed overflow Chapter 2.6 described — undefined, not merely inconvenient — which is why this chapter states the fact rather than demonstrating it.

6. The Same Bits, Two Values

Here is where this chapter and Chapter 2.6 meet, and where Chapter 2.4's value-versus-representation distinction earns its keep.

Take the pattern 1111 1111. What value is it?

Read as unsigned: all eight positions set, adding up to 255.

Read as signed: leftmost bit is 1, so flip and add one — 0000 0000 + 1 = 0000 0001 — giving −1.

Both readings are correct. The pattern does not contain the answer; the type decides how the pattern is read. This is the sharpest possible illustration of the distinction Chapter 2.4 drew: a value is what you mean, a representation is what is recorded, and the same recording can mean two different things.

You can see this in C without any new syntax, because Chapter 2.6 gave you unsigned types and C defines what happens when a negative value is converted to one:

#include <limits.h>
#include <stdio.h>

int main(void)
{
    unsigned int all_ones = -1;

    printf("all ones is %u\n", all_ones);
    printf("UINT_MAX  is %u\n", UINT_MAX);
    return 0;
}

Output:

all ones is 4294967295
UINT_MAX  is 4294967295

Storing −1 into an unsigned object produced the largest value that object can hold — which is the all-ones pattern, at this machine's full int width rather than the eight bits used in the diagrams. The bits that represent −1 are exactly the bits that represent the unsigned maximum. Read one way they are −1; read the other they are 4294967295.

7. What You Should Be Able to Say Now

1. Bits cannot store a minus sign, so negative values need an encoding — a convention for which patterns mean negative values.
2. The obvious sign-flag scheme fails: it has two zeros, and ordinary addition gives wrong answers.
3. Two's complement is derived from one requirement: a number plus its negative must give zero using ordinary addition.
4. Flip every bit, then add one. Flipping reaches all-ones; adding one rolls over to zero. That is the whole derivation.
5. The same operation converts in both directions.
6. The leftmost bit indicates the sign and also carries negative weight; reading it as such gives the same answer.
7. There is exactly one zero, which is why the range is lopsided: the most negative value has no positive counterpart.
8. The type decides how a pattern is read. 1111 1111 is 255 unsigned and −1 signed, and neither reading is more correct.
9. C23 mandates two's complement; C17 permits alternatives that no implementation you will meet uses.

8. Exercise

All bit work at the 8-bit teaching width from §1.

Exercise 1 — encode. Write the 8-bit two's complement pattern for −1, −2, −8 and −128. Show the flip-and-add-one working for at least one of them.

Exercise 2 — decode. What value does each pattern represent, read as an 8-bit signed value? 1111 1110, 1000 0000, 0111 1111, 1111 0000.

Exercise 3 — read it twice. For 1010 0000, give the value read as unsigned and the value read as signed. Then explain in one sentence what determines which is correct in a given program.

Exercise 4 — check the arithmetic. Add the 8-bit patterns for +12 and −12 using ordinary binary addition and show that the result is zero. Say what happens to the carry.

Exercise 5 — explain the asymmetry. Why does an 8-bit signed type run from −128 to +127 rather than −127 to +127 or −128 to +128? Answer by counting patterns, not by quoting the range.

Exercise 6 — reason about the edge. Using §5, explain why negating the most negative value of a signed type is a problem, and say which of Chapter 1.3's four behaviour categories it falls into.

9. Summary

• Bits have no minus sign, so negatives need a convention for which patterns mean what.
• The sign-flag idea fails — two zeros, and ordinary addition gives the wrong answer.
• Two's complement is what you get when you require that a number plus its negative be zero under ordinary addition. The machine then needs one adder and no special cases.
• Flip every bit, then add one, in either direction. Flipping reaches all-ones; adding one rolls over.
• One zero, and a lopsided range. 256 patterns, one for zero, 255 left to split unevenly — so the most negative value has no positive counterpart.
• The type decides how a pattern is read. The same bits are 255 or −1, and C lets you see this directly by converting −1 to an unsigned type.
• C23 mandates two's complement; C17 allows alternatives that are not a live concern.

Every value so far has been a whole number, and every pattern has been read as a quantity. The next chapter takes the same eight bits and reads them as something else entirely — a letter — which turns out not to be a different kind of storage at all, but the same integer storage with a different interpretation layered on top.