1. Home
2. Academy
3. Digital Logic from Zero
4. Volume 01

1.1 Binary: counting with two digits

Binary is counting with just two digits, 0 and 1. Each place is worth twice the place to its right: 1, 2, 4, 8 and so on. A binary number is the sum of the places that hold a 1.

How ordinary numbers work

Every day we count in decimal, with ten digits, 0 to 9. In a number like 407, each place is worth ten times the place to its right:

407 = 4×100 + 0×10 + 7×1 = 407

The number of digits, ten, is called the base. Nothing about ten is special. It is simply how many fingers we have.

Places in binary

Binary works the same way with base 2. There are only two digits, so each place is worth twice the place to its right. For eight bits, the places are worth:

place values: 128 64 32 16 8 4 2 1

To read a binary number, write each place's value under it, then add up the places that hold a 1. The places that hold a 0 add nothing, so you can skip them:

1101 = 1×8 + 1×4 + 0×2 + 1×1 = 13
1101 = 8 + 4 + 1 = 13
10110 = 16 + 4 + 2 = 22

The rightmost bit is worth 1, the least of any place. It is called the least significant bit, or LSB. The leftmost bit is worth the most, so it is the most significant bit, or MSB.

When a number could be read either way, books write its base as a small number after it. So 1101₂ = 13₁₀: "one one zero one in binary is thirteen in decimal".

Counting in binary

Look down the rightmost column: that bit flips at every step. The next bit flips every two steps, and the one after that every four. Volume 08 builds counters that do exactly this.

How big a number fits?

Four bits make 16 patterns, and one of them is 0, so the largest value is 15. The same goes for any number of bits: n bits give 2ⁿ patterns, and the largest value is one less.

Four bits are called a nibble, and eight bits a byte.

Adding in binary

Binary addition uses the same method as decimal addition, with fewer facts to learn:

0 + 0 = 0; 0 + 1 = 1; 1 + 1 = 10; 1 + 1 + 1 = 11

1 + 1 = 10 is simply "two", written in binary. So you write 0 and carry 1 into the next column, just as 5 + 7 in decimal means writing 2 and carrying 1. Here is 6 + 7, worked from the right:

carry  1 1 0
       0 1 1 0   (6)
     + 0 1 1 1   (7)
       -------
       1 1 0 1   (13)

The carry row shows each carry above the column it goes into. The rightmost column never has a carry into it.

Sometimes the answer needs one bit more than the numbers you added:

carry  1 1 1 0
         1 0 1 1   (11)
     +   0 1 1 0   (6)
       ---------
       1 0 0 0 1   (17)

Two 4-bit numbers gave a 5-bit answer, because 17 is more than 15. Volume 06 builds the circuit that adds, and deals with that extra bit.

1.2 Hexadecimal and octal

Long strings of bits are hard to read. Hexadecimal, or hex, writes each group of four bits as one digit - 0 to 9, then A to F - so a byte is always exactly two hex digits.

Try reading 110101111010 aloud, or copying it without a slip. Now try D7A. Both are the same number, but one is far easier for people to handle. Computers still work in binary; hex is only a shorter way for us to write it.

Sixteen digits

Hex is base 16, so it needs sixteen digits. After 9 it borrows the letters A to F:

Four bits make exactly 16 patterns, and hex has exactly 16 digits. That match is the whole trick.

Binary to hex

Split the bits into groups of four, starting from the right. Then write each group as one hex digit. If the leftmost group is short, fill it with 0s in front:

10110110 -> 1011 0110 -> B 6
110101111010 -> 1101 0111 1010 -> D 7 A
1011010 -> 0101 1010 -> 5 A

Programmers write 0x in front of a hex number, as in 0xB6, so that nobody mistakes it for decimal. Books often write B6₁₆ instead.

grouped from the left by mistake: 1011 010 -> B 2 = 0xB2 = 178
1011010 = 0x5A = 90

Hex to binary

Going back is just as quick. Each hex digit becomes exactly four bits:

3F -> 0011 1111
C8 -> 1100 1000
7EA -> 0111 1110 1010

Where you meet hex

Colours on web pages are written as three bytes in hex, one each for red, green and blue. The colour #FF8800 is a bright orange:

red FF = 255
green 88 = 136
blue 00 = 0

Memory addresses and the contents of registers are nearly always written in hex too, because each digit maps straight onto four bits.

Octal

Octal is base 8. It does the same job as hex with groups of three bits, and uses only the digits 0 to 7:

101110 -> 101 110 -> 56 (octal) = 46
octal 755 -> 111 101 101

Octal is less common than hex, but you still meet it in file permissions on Linux and macOS. Permission 755 gives the owner read, write and run (111), and everyone else read and run (101).

1.3 Converting between bases

To turn a decimal number into binary, divide it by 2 again and again, and read the remainders from the bottom up. To turn binary or hex into decimal, add up the place values.

Decimal to binary: divide by 2

Divide by 2 and write down the remainder, which is always 0 or 1. Then divide the answer by 2 again. Stop when the answer reaches 0:

13 / 2 = 6 remainder 1
6 / 2 = 3 remainder 0
3 / 2 = 1 remainder 1
1 / 2 = 0 remainder 1
read upwards: 13 = 1101

Why read upwards? The first remainder says whether the number is odd, and only the 1s place can make a number odd. So the first remainder is the rightmost bit, and each later remainder is the next bit to the left.

A bigger example works the same way:

156 / 2 = 78 remainder 0
78 / 2 = 39 remainder 0
39 / 2 = 19 remainder 1
19 / 2 = 9 remainder 1
9 / 2 = 4 remainder 1
4 / 2 = 2 remainder 0
2 / 2 = 1 remainder 0
1 / 2 = 0 remainder 1
read upwards: 156 = 10011100

A shortcut: take away powers of two

For numbers up to a few hundred, it is often quicker to take away the biggest place value that fits, again and again:

156 - 128 = 28
28 - 16 = 12
12 - 8 = 4
4 - 4 = 0
156 = 128 + 16 + 8 + 4 -> 1001 1100

The places you took away get a 1, and every other place gets a 0.

Decimal to hex: divide by 16

The dividing method works for any base. For hex, divide by 16, and write each remainder from 10 to 15 as a letter:

2026 / 16 = 126 remainder 10 (A)
126 / 16 = 7 remainder 14 (E)
7 / 16 = 0 remainder 7 (7)
read upwards: 2026 = 0x7EA

Back to decimal

The places in hex are worth 1, 16, 256, 4096 and so on, each sixteen times the last. Multiply each digit by its place and add:

0x7EA = 7×256 + 14×16 + 10×1 = 2026

Octal and hex, through binary

To convert between octal and hex, go through binary. Write each octal digit as three bits, then regroup the bits in fours:

octal 57 -> 101 111 -> 0010 1111 -> 0x2F

0.625 x 2 = 1.25 -> 1
0.25 x 2 = 0.5 -> 0
0.5 x 2 = 1 -> 1
0.625 = 0.101

0.1 x 2 = 0.2 -> 0
0.2 x 2 = 0.4 -> 0
0.4 x 2 = 0.8 -> 0
0.8 x 2 = 1.6 -> 1
0.6 x 2 = 1.2 -> 1
0.2 x 2 = 0.4 -> 0
0.4 x 2 = 0.8 -> 0
0.8 x 2 = 1.6 -> 1
0.6 x 2 = 1.2 -> 1
0.2 x 2 = 0.4 -> 0
0.1 = 0.0001100110... (it never ends)

0.1 + 0.2 in 64-bit floating point = 0.30000000000000004

1.4 Negative numbers: two's complement

A computer has no minus sign, only bits. In two's complement, the top bit simply counts as a negative place: in 8 bits it is worth -128 instead of +128. With that one change, the same adding circuit works for positive and negative numbers.

A number that can be negative is a signed number. Every signed number needs some way to show its sign using nothing but 0s and 1s.

First try: a sign bit

The obvious idea is to keep the top bit for the sign: 0 for plus and 1 for minus. The other bits hold the size. This is called sign-magnitude:

+5 = 0000 0101
-5 = 1000 0101

It has two problems. There are two zeros, which wastes a pattern and makes comparing numbers harder. Worse, ordinary binary addition gives nonsense:

zero twice: +0 = 0000 0000, -0 = 1000 0000
0000 0101 + 1000 0101 = 1000 1010, which sign-magnitude reads as -10

5 + (-5) should be 0, not -10. A computer using sign-magnitude would need extra circuits to add signed numbers.

Two's complement: the top place is negative

Two's complement keeps every place value the same, except the top one, which becomes negative. In 8 bits, the top bit is worth -128:

Read -5 the same way:

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

Making a number negative: invert and add 1

You do not have to work out the weights to find a negative number. Start from the positive number, flip every bit, then add 1:

+5 = 0000 0101
invert: 1111 1010
add 1: 1111 1011 = -5

Now add 5 and -5 with the ordinary rules:

carry  1 1 1 1 1 1 1 1
         0 0 0 0 0 1 0 1   (5)
     +   1 1 1 1 1 0 1 1   (-5)
       -----------------
       1 0 0 0 0 0 0 0 0
the ninth bit does not fit in 8 bits and is dropped
keep 8 bits: 0000 0000 = 0

The carry out of the top bit falls off the end, and the answer is exactly 0. That is the whole reason computers use two's complement: one adding circuit handles positive and negative numbers alike.

All sixteen 4-bit patterns

Here is every 4-bit pattern, read as an ordinary unsigned number and as two's complement:

Figure 1.3 puts the same patterns round a wheel. Adding 1 always moves one step clockwise, whether the numbers are positive or negative.

Three things stand out:

1. Every negative number starts with 1, so the top bit still shows the sign at a glance.
2. There is only one zero. The pattern that sign-magnitude wasted is now -8.
3. There is one more negative number than positive. -8 has no +8 partner, because +8 does not fit in 4 bits.

How far the numbers go

With n bits, two's complement runs from -2^n-1 up to 2^n-1 - 1:

The lowest number is its own odd one out. Negate it with the usual rule and you get it straight back, because its positive partner does not fit:

-128 = 1000 0000; invert: 0111 1111; add 1: 1000 0000 = -128

Sign extension

To copy a signed number into more bits, repeat its top bit into all the new places. This is called sign extension, and it keeps the value the same:

1011 (-5) -> 1111 1011 (-5)
0101 (5) -> 0000 0101 (5)

1000 0101 in two's complement = -128 + 4 + 1 = -123

1.5 Codes: BCD, Gray code and ASCII

Not every pattern of bits is a number to do sums with. A code gives patterns an agreed meaning: BCD stores decimal digits, Gray code changes one bit at a time, and ASCII stores letters.

BCD: one decimal digit per nibble

Binary-coded decimal, or BCD, keeps each decimal digit in its own four bits:

59 in BCD = 0101 1001; 59 in binary = 0011 1011

BCD is easy to show on a display, because each nibble drives one digit. Clocks, meters and calculators use it. The price is space. Six of the sixteen nibble patterns are never used, and big numbers need more bits:

never used in BCD: 1010 1011 1100 1101 1110 1111
999 in BCD = 1001 1001 1001 (12 bits); in binary = 1111100111 (10 bits)

Gray code: one bit at a time

In ordinary binary, some steps change several bits at once. Going from 3 to 4, all three bits change. In Gray code, every step changes exactly one bit:

bits that change at each step, binary: 1 2 1 3 1 2 1 3
bits that change at each step, Gray:   1 1 1 1 1 1 1 1

Why does it matter? Picture a sensor that reads the position of a turning knob. If it reads while the position is changing from 3 to 4 in binary, some bits may have changed and others not yet. The reading could be any of the eight values. In Gray code only one bit moves, so a reading taken mid-change is either the old value or the new one:

binary 011 -> 100 changes 3 bits; Gray 010 -> 110 changes 1

To turn binary into Gray code, copy the first bit. Then compare each pair of neighbouring binary bits: the same gives 0 and different gives 1.

binary 1011 -> Gray 1110
first bit copied: 1
1 and 0: differ -> 1
0 and 1: differ -> 1
1 and 1: same -> 0

To go back, copy the first bit again. Then compare each Gray bit with the binary bit you have just worked out: the same gives 0 and different gives 1.

Gray 1110 -> binary 1011
first bit copied: 1
Gray bit 1, binary bit before it 1: same -> 0
Gray bit 1, binary bit before it 0: differ -> 1
Gray bit 0, binary bit before it 1: differ -> 1

"Same gives 0, different gives 1" is a rule you will meet again. Volume 02 turns it into a gate.

ASCII: letters as numbers

To store text, every character needs a number. ASCII is the standard code for English letters, digits and punctuation. It uses 7 bits, which make 128 codes:

The code was laid out with care. Capital and small letters differ by 32, which is one bit. The digit characters start at 0x30, so taking 0x30 away turns a digit character into its value:

A = 1000001, a = 1100001: they differ by 32, one bit
'7' = 0x37; take away 0x30 -> 7
"Hi" = 0x48 0x69

A parity bit

A byte has room for 8 bits, but ASCII needs only 7. The spare bit can be a parity bit, chosen to make the number of 1s even. If any single bit is flipped on the way, the count of 1s turns odd, and the receiver knows something went wrong:

A = 1000001: 2 ones -> parity bit 0 -> 01000001
C = 1000011: 3 ones -> parity bit 1 -> 11000011

0100 0001: unsigned 65, ASCII 'A', BCD 41

What you learned

• Binary is base 2: each place is worth twice the place to its right, and a number is the sum of the places that hold a 1.
• n bits make 2 to the power n patterns, from 0 up to 2 to the power n, minus 1.
• Binary addition works like decimal: 1 + 1 = 10, so write 0 and carry 1.
• Hex writes each group of four bits as one digit, 0 to F; octal does the same with groups of three.
• To convert decimal to binary, divide by 2 and read the remainders upwards; to go back, add the place values.
• Two's complement makes the top place negative. To negate, invert every bit and add 1.
• n-bit two's complement runs from -2 to the power n-1 up to 2 to the power n-1, minus 1, and has one zero.
• BCD stores decimal digits, Gray code changes one bit per step, and ASCII stores characters in 7 bits.

Key words from this volume

Every word below has a plain-English entry in the glossary.

• Binary
• Decimal
• Base (of a number)
• LSB (least significant bit)
• MSB (most significant bit)
• Nibble
• Byte
• Carry
• Hexadecimal
• Octal
• Two's complement
• Signed number
• Sign-magnitude
• Sign extension
• Ones' complement
• BCD (binary-coded decimal)
• Gray code
• ASCII
• Parity bit

Practice

200 / 2 = 100 remainder 0
100 / 2 = 50 remainder 0
50 / 2 = 25 remainder 0
25 / 2 = 12 remainder 1
12 / 2 = 6 remainder 0
6 / 2 = 3 remainder 0
3 / 2 = 1 remainder 1
1 / 2 = 0 remainder 1

200 = 1100 1000 = 0xC8

0x3A7 = 3×256 + 10×16 + 7×1 = 935

-100: +100 = 0110 0100; invert: 1001 1011; add 1: 1001 1100

1110 0110 = -128 + 64 + 32 + 4 + 2 = -26

2026 in BCD = 0010 0000 0010 0110; in binary = 111 1110 1010 (11 bits)

13 = 1101 in binary = 1011 in Gray code

12 bits, signed: -2048 to 2047

Interview corner

another way: 256 - 5 = 251 = 1111 1011

Volume 02 puts these bits to work: it meets the seven logic gates and the rules each one follows.