Numbers in Binary

At the end of the last chapter we had a row of full adders that could add two numbers, as long as both were positive and the answer fit. Real programs need more. Your bank balance can go below zero. A game character can move left as well as right. A thermometer can read −5°.

But a computer has no "minus sign" switch. Everything has to be made of bits. Before we tackle that puzzle, let's fix a more everyday problem: binary numbers are very hard for humans to read.

Hexadecimal: binary for humans

Quick: is 1011100000000000 the same as 1011100000000000? You probably had to check digit by digit. Long strings of 0s and 1s are easy for circuits and miserable for people. Decimal doesn't help much either, because there's no simple link between decimal digits and bits: you can't tell which bits are on in 47,104 without doing arithmetic.

The fix is lovely. Split the bits into groups of four, starting from the right. Four bits can make exactly 16 patterns, from 0000 to 1111. So give each pattern its own single-character digit. We need 16 digits, so after 0–9 we borrow the letters A to F:

This is hexadecimal, or hex for short: base 16. A group of four bits is called a nibble (half a byte, a programmer's joke), and each nibble is exactly one hex digit. That ugly number above is just B800.

To show that a number is hex rather than decimal, programmers usually write 0x in front: 0x10 is sixteen, not ten. You'll meet hex everywhere once you start looking:

• Memory addresses in debuggers and crash messages, like 0x7ffd4a2c.
• Colors on the web: #FF8800 is three bytes, FF red, 88 green and 00 blue, which makes orange.
• Raw bytes in files, network packets and machine code. One byte is always exactly two hex digits, from 00 to FF.

The trouble with minus signs

Back to negative numbers. The most obvious idea is to steal one bit for the sign: say the leftmost bit means "minus" when it's 1, and the remaining bits hold the size of the number. In 4 bits, 0010 would be +2 and 1010 would be −2. This is called sign-magnitude, and it's how we write numbers on paper.

Some early computers really worked this way, but it causes two headaches:

• There are two zeros. 0000 is +0 and 1000 is −0. Every comparison has to remember that they're equal.
• Our adder gives nonsense. Feed it +2 and −2 and it happily adds the bit patterns:

    0 0 1 0     +2
  + 1 0 1 0   + −2
  ---------   ----
    1 1 0 0     −4  ← wrong! should be 0

We'd need a separate subtracting circuit, plus logic to decide which one to use. There's a much better way, and it comes from an unexpected place: a car's odometer.

The odometer trick

Imagine a 4-digit odometer showing 0000. Wind it backwards by one mile. It doesn't show a minus sign; it rolls over to 9999. And look: if you then drive forward one mile, 9999 becomes 0000 again. So 9999 behaves exactly like −1.

Binary works the same way. Our 4-bit adder already wraps around: 1111 + 0001 = 0000 (with a carry falling off the end). So 1111 acts like −1, 1110 like −2, and so on. Let's just call them that. Arrange all 16 patterns in a circle, like the wheel inside the odometer:

This scheme is called two's complement, and every modern computer uses it. Notice what you get for free:

• One zero. 0000 is the only zero.
• A sign bit, without trying. Every negative number starts with 1 and every positive one starts with 0. You can tell the sign at a glance.
• The adder just works. −2 + 2 is 1110 + 0010 = 1 0000. The carry falls off the end and the 4 bits left are 0000. Zero, as it should be.

The range is a little lopsided. 4 bits give −8 to +7: there are 8 negative numbers, zero, and only 7 positive ones. A byte (8 bits) holds −128 to +127.

Negating: flip the bits and add one

Given a number, how do we find its negative? There's a two-step recipe that always works:

1. Flip every bit: every 0 becomes 1 and every 1 becomes 0. That's just a row of NOT gates.
2. Add 1.

Why does it work? Add any number to its flipped self, say 0101 + 1010. Every column is a 1 plus a 0, so you always get 1111, which is −1. So "x flipped" equals −1 − x, and adding 1 gives exactly −x.

The name comes from this too. In 4 bits, a number and its negative always add up to 16, which is 2⁴. The negative is the "complement" with respect to a power of two.

Subtraction for (almost) free

Here's the payoff. Subtracting B is the same as adding −B:

A − B  =  A + (−B)  =  A + (NOT B) + 1

So to turn our adder into a subtractor we need two things: a way to flip all of B's bits, and a way to add 1. Both are already within reach:

• Flipping, on demand. Look back at XOR's truth table. B XOR 0 is just B, while B XOR 1 is NOT B. So an XOR gate is a controllable inverter. Put one on each B input and connect them all to a single control wire, which we'll call SUB.
• The +1. Remember the carry-in of the rightmost full adder, which we tied to 0 in Chapter 1? Connect it to SUB instead. When we subtract, it adds the 1 we need.

Four XOR gates and one wire turned an adder into an adder and subtractor. This little circuit is the heart of the arithmetic logic unit (ALU), the part of a processor that does the math. We'll build a full ALU when we design our toy CPU in Part II.

One pattern, two meanings

Now for the strangest and most important idea in this chapter. Look at the result 1110. Is it 14 or −2? It's both. The bits don't know. The adder didn't care either: the exact same circuit gave the right answer for both readings.

The only thing that differs is how you detect a wrong answer:

• Unsigned overflow happens when the result runs past 15 or below 0. The circuit spots it with the final carry. x86 stores this in the carry flag (CF). For subtraction CF means "borrow", so it's set when you take a bigger number from a smaller one.
• Signed overflow happens when the result crosses the seam between +7 and −8. Adding two positive numbers and getting a negative one is the classic sign. x86 stores this in the overflow flag (OF). In the circuit, it's on when the carry into the sign bit differs from the carry out of it, which takes just one more XOR gate.

The CPU computes both flags on every addition and lets the program decide which one matters. That's why x86 has two families of "jump if smaller" instructions: jb ("below") for unsigned numbers and jl ("less") for signed ones. In C, it's the difference between unsigned int and int: the bits are the same, but the compiler picks different instructions.

mov  al, 0x7F      ; al = 127 (al is the lowest byte of rax)
add  al, 1         ; al = 0x80
                   ;   unsigned: 128, fine            → CF = 0
                   ;   signed:  −128, overflow!       → OF = 1
neg  al            ; flip and add one: al = 0x80 again (−128 has no +128)

RISC-V, with no flags at all, simply provides separate instructions: blt and bltu branch if less than (signed and unsigned), and slt / sltu set a register to 1 or 0. It doesn't even need a "negate" instruction. Register zero always holds 0, so −x is just 0 − x:

li   a0, 3
li   a1, 5
sub  a2, a0, a1      # a2 = −2  (0xFFFFFFFFFFFFFFFE in 64 bits)
sub  a3, zero, a2    # a3 = 0 − (−2) = 2   (assemblers also accept "neg a3, a2")

Making numbers wider: sign extension

Programs often need to move a number from a small box into a bigger one, for example from an 8-bit byte into a 64-bit register. For a positive number you just add zeros on the left. But a negative number needs more care. Look at −5:

 8 bits:           1111 1011   = −5
16 bits, wrong:    0000 0000 1111 1011   = 251   ← padded with zeros
16 bits, right:    1111 1111 1111 1011   = −5    ← padded with copies of the sign bit

Copying the sign bit into all the new places is called sign extension. Padding with zeros is zero extension, the right choice for unsigned numbers. Once again the CPU can't know which you meant, so it offers both: x86 has movsx and movzx, and RISC-V has lb ("load byte", sign-extended) and lbu (zero-extended).

Try it yourself

1. What is 0xFF in decimal? What about 0x100?
   Show answer

   0xFF = 1111 1111 = 255, the biggest byte. 0x100 = 256: it's "1 followed by two zeros" in base 16, so 16 × 16.
2. In 4-bit two's complement, what number is 1110? And 1000?
   Show answer

   1110 = −8 + 4 + 2 = −2. 1000 = −8, the most negative 4-bit number.
3. Using the negation demo, what does −1 look like in 8 bits? Why does that make sense on the odometer?
   Show answer

   1111 1111 (0xFF). It's the pattern just "behind" zero on the wheel: add 1 and it rolls over to 0000 0000.
4. Set the adder-subtractor to 3 − 5. Which reading of the result is correct, and which flag is set?
   Show answer

   The result is 1110. As a signed number it's −2, which is correct. As an unsigned number it's 14, which is wrong, since 3 − 5 can't be done without going below zero. So CF = 1 (a borrow) and OF = 0.
5. Why can 8-bit two's complement hold −128 but not +128?
   Show answer

   8 bits make 256 patterns. Half of them (those starting with 1) are negative: −1 to −128. The other half start with 0, and one of those is zero, leaving only 127 for the positives.

What we learned

• Hexadecimal writes each group of 4 bits (a nibble) as one digit from 0 to F. One byte is always two hex digits.
• Two's complement treats the patterns past the halfway point of the "odometer" as negative. There's one zero and a free sign bit, and the ordinary adder just works.
• To negate a number: flip every bit, then add 1.
• A − B = A + NOT B + 1. XOR gates and the carry-in turn an adder into an adder-subtractor, the heart of an ALU.
• The same bits can mean an unsigned or a signed number. The CPU computes both kinds of overflow (CF and OF on x86) and the program decides which matters.
• Widening a signed number needs sign extension; an unsigned one needs zero extension.

So far our circuits have no memory. The moment you let go of an input, the answer vanishes. A computer has to remember things: the numbers it's working on, the program it's running, where it's up to. In the next chapter we'll do something that sounds like a mistake: wire a gate's output back into its own input. That loop is how circuits remember.