Numbers in binary

Combining gates started counting in binary: each bit is worth twice the one to its right, so 1101 is 8 + 4 + 1 = 13. This page is about what a processor actually does with that. Its numbers live in registers, rows of a fixed number of bits, and a fixed number of bits raises questions that pencil and paper never do. What happens when a number gets too big? How do you write −5 with only 0s and 1s? And where does the point go in 2.75?

The figures use the same colours as the other pages: orange is 1, grey is 0. Click a bit to flip it.

1 · Bytes, and why eight

A group of eight bits is a byte. Eight bits make 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 = 256 patterns, so a byte holds 0 to 255. In general, n bits make 2ⁿ patterns: every extra bit doubles them. Sixteen bits make 65,536, and 32 bits about 4.3 billion.

Eight wasn’t inevitable. Early computers used all sorts of sizes: words of 12, 18, 36 or 60 bits, with characters of 6 bits, which make 64 symbols: enough for capital letters, digits and punctuation, but no lower case. Older teleprinters used just 5 bits, 32 symbols, with special “shift” codes to switch between letters and figures.

Eight won in 1964, when IBM built its whole System/360 range of computers around an 8-bit byte. (The word byte was coined in 1956 by Werner Buchholz, at IBM, for a group of bits of any size.) Eight bits had three things going for them:

Room for text: 256 symbols are plenty for upper and lower case and more. The ASCII standard of 1963 needed 7 bits; IBM’s own code used all 8.
Two decimal digits per byte: a digit from 0 to 9 needs 4 bits, so a byte holds exactly two. Business computing did its sums in decimal, and this mattered.
A power of two: picking one of 8 bits takes exactly 3 bits of address, and 16-, 32- and 64-bit words split evenly into bytes.

The 8-bit microprocessors of the 1970s, such as the Intel 8080 and the 6502, settled it for good, and every computer since counts memory in bytes.

2 · Hexadecimal

Long rows of 0s and 1s are hard to read and easy to get wrong. Decimal is no help: there’s no simple way to see the bits in 205. So programmers use hexadecimal (hex), base 16, because 16 is 2 × 2 × 2 × 2: each hex digit is exactly four bits. Hex needs sixteen digits, so after 0 to 9 it borrows the letters A to F:

bits	0000	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011	1100	1101	1110	1111
hex	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
value	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15

To turn bits into hex, split them into fours from the right and look each group up: 0011 1100 is 3C. A byte is always two hex digits, 00 to FF. To make clear that a number is hex, it gets a prefix: 0x3C in most programming languages, or $3C in 6502 assembly.

Click the bits: each group of four (shaded) is one hex digit, shown underneath. New target gives you a number in hex to make: work out each digit’s four bits from the table, and the decimal value looks after itself. With 16 bits, the register holds 0x0000 to 0xFFFF, which is exactly how many addresses a 6502 has: 65,536.

Hex is everywhere once you look. A colour on a web page, #FF8800, is three bytes: red FF (255), green 88 (136) and blue 00, which makes orange. Memory addresses, error codes and network card addresses are all written in hex, because the bits are what matter and hex shows them compactly.

3 · Running out of room

On paper, a number can always grow another digit. A register can’t: four bits hold 0 to 15, and there is no 16. Add 1 to 1111 and every bit rolls over, like an odometer: 0000. The 1 that should have gone into a fifth place has nowhere to go. That’s wrapping round, and it’s easiest to see with the numbers drawn in a circle.

The 16 patterns of 4 bits, round a wheel: the bits on the outside, the number they make inside. Click +1 to step clockwise and −1 to step back. Every step is right, except one: across the marked line, 15 + 1 gives 0, and 0 − 1 gives 15. The numbers wrap round.

Wrapping round isn’t always a mistake. Sometimes it’s exactly what’s wanted: the oscillators in the SID sound chip are counters that wrap round on purpose, hundreds or thousands of times a second, and each trip round the wheel is one cycle of the note.

4 · Negative numbers

A register only has 0s and 1s: no minus sign. So some of the patterns have to mean negative numbers. The obvious way is to give up one bit to be the sign: 0 for plus, 1 for minus, with the other bits saying how big. That’s sign and magnitude, and it’s how we write numbers on paper. It has two problems. There are two zeros, 0000 (+0) and 1000 (−0). And worse, ordinary adding stops working: going up from −3 (1011) by one gives the next pattern, 1100, which is −4.

The fix is to look at the wheel again. Going back one step from 0 lands on 1111. So call 1111 −1: it’s the number that, plus 1, gives 0. The one before it, 1110, is −2, and so on round, until the patterns starting with 1 are −1 to −8 and those starting with 0 are 0 to 7. That’s two’s complement. The top bit still tells you the sign, but it’s not a separate sign: it’s simply worth −8 instead of +8 (in a byte, −128 instead of +128). So 1101 is −8 + 4 + 1 = −3.

The same wheel, with three ways of reading the same bits; the negative numbers are shaded. Start with two’s complement and step through zero both ways: −1 + 1 = 0, just as it should. The only bad step is across the marked line, between 7 and −8. Then switch to sign and magnitude and try going up from −3: it goes the wrong way, and there are two zeros.

The great thing about two’s complement is what doesn’t change. Stepping round the wheel is the same whichever way you read it, so the same circuit adds signed and unsigned numbers: it doesn’t need to know which it’s doing. Some early computers used sign and magnitude, or a cousin of it, ones’ complement (with two zeros as well); processors for decades now have all used two’s complement.

5 · Making a number negative

To turn 5 into −5 in two’s complement, there’s a recipe: flip every bit, then add 1.

Click the bits of x in the top row. The second row is every bit flipped, and the third adds 1 to it, giving −x. The place values along the top are two’s complement ones: the leftmost bit is worth −128. Try 0, and try 1000 0000 (−128).

Why it works: a number and its flipped self have no 1s in common and no 0s in common, so added together they make all 1s, 1111 1111, which is −1. So the flipped number is −1 − x, and adding 1 gives −x.

Two numbers are odd ones out. Flipping 0 gives all 1s, and adding 1 wraps round to 0 again: minus 0 is 0, as it should be, with only one zero. And −128 has no opposite: 8 bits stop at +127. Flip −128 and add 1, and you’re back at −128.

6 · Adding, and two ways to overflow

Adding builds the adder from gates; here what matters is what its answer means. An 8-bit adder takes two bytes and makes a byte. If the true answer doesn’t fit, something has gone wrong, and there are two different ways it can go wrong:

Carry, for unsigned numbers: the sum went past 255 and wrapped round. The 1 that should have gone into a ninth bit comes out of the adder as the carry.
Overflow, for signed numbers: the sum went past +127 or below −128. You can spot it from the signs alone: two positives that add up to a negative, or two negatives that add up to a positive.

The adder doesn’t know whether its inputs are signed, so a processor works out both and keeps them in two flags, single bits the next instruction can test. The 6502 calls them C and V.

Two bytes added, read both ways. 100 + 50 is 150 unsigned, which fits; but as signed numbers, two positives have made −106: overflow. 200 + 100 is the opposite: as unsigned it’s 300, which doesn’t fit (carry), but as signed it’s −56 + 100 = 44, which is right. 255 + 1 carries, yet as signed it’s −1 + 1 = 0, perfectly correct. And −128 + −128 sets both. Click the bits to try your own.

So a carry isn’t always an error: it depends on what the numbers mean, which only the program knows. Adding numbers bigger than a byte uses it on purpose: add the low bytes, then add the high bytes plus the carry, just like carrying a 1 in long addition.

Overflow matters in sound, too. An audio sample is stored as a two’s-complement number (16 bits of it, on a CD; the Sampling page has what the bits buy), and a sample that overflows doesn’t just stop at the loudest value: it wraps round to the most negative one, a full-scale jump that sounds like a loud crack. So audio code uses saturating arithmetic, which stops at the largest number instead of wrapping: clipping sounds bad, but wrapping sounds far worse.

7 · Shifts

In decimal, putting a 0 on the end multiplies by ten: 13 becomes 130. In binary, moving every bit one place left multiplies by two: 1101 (13) becomes 11010 (26). That’s a shift left, and moving every bit one place right, a shift right, halves (dropping the bit that falls off the end, so it rounds down). Shifts are among the cheapest things a processor does, so multiplying or dividing by 2, 4, 8 and so on is nearly free.

A shift right has a choice to make: what comes in at the left? For unsigned numbers, a 0. But for a negative number in two’s complement, a 0 at the top would make it positive. So there are two kinds of shift right:

Logical shift right brings in a 0. It halves an unsigned number.
Arithmetic shift right copies the top bit, the sign, back in. It halves a signed number and keeps it negative.

A shift left is the same either way: a 0 comes in at the right.

Shift and watch: the dashed box marks the bit that came in, and the one that fell off the end is shown beside the register. From 13, a shift left doubles; a shift right halves. Now start from −6: a logical shift right gives 125, nonsense as a signed number, while an arithmetic shift gives −3. From −7, an arithmetic shift gives −4, not −3: shifting rounds down, towards minus infinity, and −3.5 rounds down to −4.

Processors usually have instructions for both: ARM, for example, has LSR and ASR. The 6502 has only the logical one, LSR, and an arithmetic shift left, ASL, which is the same as a logical one. On most processors, including the 6502, the bit that falls off the end goes into the carry flag, so a program can catch it.

8 · Fractions: fixed point

Bits after a point work just like digits after a decimal point. In decimal, the places after the point are worth a tenth, a hundredth and so on; in binary they’re worth a half, a quarter, an eighth, each half the one before. So 10.11 in binary is 2 + ½ + ¼ = 2.75.

A register has no room for a point. But it doesn’t need one: the program just agrees where it is. Say a byte has 4 bits before the point and 4 after. Then 0010 1100 means 0010.1100, which is 2.75. Underneath, the register holds the whole number 44, and 44 ÷ 16 = 2.75: a fixed-point number is a whole number with an agreed scale. One common way to write the format down is Q4.4: 4 bits before the point, 4 after.

Click the bits, and choose how many come after the point: the place values along the top follow it. Fewer bits after the point give a bigger range; more give finer steps; with 8 bits, every choice is a trade between the two. New target picks a number to make. Untick Signed to read the bits unsigned, with no negatives.

Fixed point is attractive because almost nothing new is needed. Adding two fixed-point numbers with the point in the same place is just adding the whole numbers underneath: 2.75 + 1.5 is 44 + 24 = 68, and 68 ÷ 16 = 4.25. The same adder, the same carry and overflow, as if the point weren’t there.

Multiplying needs one more step. The whole numbers underneath are each 16 times too big, so their product is 16 × 16 times too big: it has 8 bits after the point instead of 4. A shift right by 4 puts the point back.

Two Q4.4 numbers (signed: −8 to 7.9375, in steps of 1/16) multiplied. Multiply the whole numbers underneath, 40 × 24 = 960 for 2.5 × 1.5, and the product has 16 bits with 8 after the point; an arithmetic shift right by 4 brings it back to Q4.4: 3.75. Try something small, like 0.0625 × 0.0625: the answer is too small for the format, and the shift rounds it down to 0. Try 3 × 3 = 9: too big for 4 whole bits.

Fixed point is how most digital signal processing was done for decades, and still is wherever chips have to be small and cheap. Audio is often handled as Q15: a 16-bit sample read as a fraction from −1 to just under 1, so the product of two samples stays in the same range (all but one: −1 × −1). Before chips had floating point, games did their 3D maths in fixed point.

Its weakness is the fixed range. The point can’t move, so a format with fine steps can’t hold big numbers, and one with a big range can’t hold small ones precisely. Some fractions can’t be held exactly at all: 0.1 in binary is 0.000110011001100…, repeating forever, just as ⅓ is 0.333… in decimal. Every format with a fixed number of bits has to round it.

9 · One set of bits, many meanings

Every section of this page has been about the same thing: a row of bits. The bits never say what they mean. 1111 1111 is 255, or −1, or 15.9375, depending on who’s reading:

bits	unsigned	signed	Q4.4	signed Q4.4
0000 0000	0	0	0	0
0010 1100	44	44	2.75	2.75
0111 1111	127	127	7.9375	7.9375
1000 0000	128	−128	8	−8
1111 1111	255	−1	15.9375	−0.0625

The meaning is a choice the program makes, by which instructions it uses on the bits: which flag it tests after adding, which kind of shift it does. And each choice suits different jobs:

Unsigned, when a value can never be negative and the whole range is wanted for it: a count, an address, a colour’s brightness, 0 to 255.
Signed, when it can go either way: a temperature, a change in position, an audio sample, −128 to 127.
Fixed point, signed or unsigned, when it needs a fraction: a volume setting between 0 and 1, a filter’s coefficients.

Sometimes data arrives in one meaning and is wanted in another. Audio is a common case: 8-bit WAV files store their samples unsigned, with silence at 128 and the wave swinging either side of it, while 16-bit WAV files store them signed, with silence at 0. To turn an unsigned byte into a signed one centred on zero, subtract 128. And there’s a neat shortcut: subtracting 128 is the same as flipping the top bit. Look at the table: 1000 0000 (128 unsigned) becomes 0000 0000 (0); 1111 1111 (255) becomes 0111 1111 (127); 0000 0000 (0) becomes 1000 0000 (−128). Flipping one bit is a single, fast instruction (an exclusive OR with 0x80), and it works the same way in both directions.

Summary

n bits make 2ⁿ patterns. A byte is 8 bits, 0 to 255; it became the standard in the 1960s, being enough for text, two decimal digits, and a power of two.
Hexadecimal writes each group of four bits as one digit, 0 to F, so a byte is two hex digits (0x3C).
A register has a fixed number of bits, so numbers wrap round past the top.
Two’s complement holds negative numbers by making the top bit worth minus its usual value: in a byte, −128 to +127. There’s one zero, and the same adder works for signed and unsigned numbers.
To negate, flip every bit and add 1.
Carry means an unsigned sum didn’t fit; overflow means a signed one didn’t. Processors keep both as flags.
A shift left doubles; a shift right halves, logical (a 0 comes in) for unsigned numbers, arithmetic (the sign is copied in) for signed ones.
Fixed point is a whole number with an agreed scale: adding is unchanged, and multiplying needs a shift to put the point back.
The same bits can mean different numbers: unsigned, signed or fixed point is the program’s choice. Flipping the top bit converts between unsigned and signed centred on zero.