4.1 Binary numbers and adders

Why this matters

Every number a circuit handles is a row of bits, and the first thing hardware does with numbers is add them. Counting, comparing, subtracting and computing an address all reuse the same adder. This section builds it from the bottom: a rule for adding two bits, a part that also accepts the carry arriving from the column on its right, and a chain of those parts.

Learning goals

• Read an unsigned binary pattern as a number and state the range of $n$ bits.
• Add and subtract two binary numbers column by column, naming each carry and each borrow.
• Describe the half adder and the full adder by their tables and their equations.
• Explain how full adders chain into a ripple-carry adder, and why a carry may have to travel through every stage.

Intuition first

You already add on paper by columns. Starting at the right, you add the two digits in a column, write the low digit of the answer under it, and carry anything left over into the next column. Binary does the same with only two digits. A column that adds up to two or more writes its low bit and carries a 1 into the column on its left.

A circuit can do this too. Give each column its own small adder, and let the carry be a wire from one column's adder to the next. Each adder looks only at its own two bits and the carry that arrives, so every column uses the same design. The rest of the section is that picture made exact.

Binary numbers and column arithmetic

A pattern of $n$ bits can be read as an unsigned number, the reading Section 2.6 already used: the bit in position $i$ is worth $2^i$ and the value is the sum of the worth of the bits that are 1.

Definition 4.1.1(unsigned range).

An $n$-bit pattern read as an unsigned number has the value $\sum_i b_i 2^i$ and can stand for every whole number from $0$ up to $2^n-1$, and for no others. A result outside that range does not fit in $n$ bits.

Addition and subtraction work in binary with the same rules as in decimal, except that a column holds only 0 or 1. Two examples with eight-bit numbers show both rules. The first is a sum in which the carry travels through several columns.

Example 4.1.1(63 + 8 in eight bits).

The columns are numbered from 0 at the right. The first number has 1s in columns 0 to 5, and the second has a single 1, in column 3.

8-bit A + B: A is 00111111, B is 00001000; result 01000111, 71 unsigned, 71 signed; carry 0

	8-bit pattern	unsigned
A	00111111	63
+ B	00001000	8
=	01000111	71

carry = 0

Work from the right. Columns 0, 1 and 2 each add a 1 and a 0, so they write 1 and carry nothing. Column 3 adds a 1 and a 1, which is two: it writes 0 and carries 1. Column 4 adds a 1, a 0 and the carry of 1, which is again two, so it writes 0 and carries 1. Column 5 does the same. Column 6 adds a 0, a 0 and the carry, writes 1, and carries nothing, so column 7 sees only zeros. The bits written, from column 7 down to column 0, are the result row of the table. The carry out of the top column is 0, so the sum fits in eight bits.

Subtraction has a carry-like helper called a borrow: when a column's top digit is smaller than what is taken away, it borrows a 1 from the next column to its left, and that 1 is worth 2 in the column that borrowed it.

Example 4.1.2(65 − 8 in eight bits).

8-bit A − B: A is 01000001, B is 00001000; result 00111001, 57 unsigned, 57 signed; borrow 0

	8-bit pattern	unsigned
A	01000001	65
− B	00001000	8
=	00111001	57

borrow = 0

Columns 0, 1 and 2 subtract 0, so they write what was there. Column 3 has a 0 on top and must take away a 1, so it borrows from column 4, which is also 0 and so has to borrow from column 5, which is 0 as well, and that borrows from column 6, which holds the number's only other 1. Column 6 gives up its 1 and becomes 0. Columns 5 and 4 each receive a 2, lend one of it on and keep 1. Column 3 receives a 2, takes away the 1 and keeps a 1. The result row reads 1 in columns 5, 4, 3 and 0, and nothing is borrowed out of the top, so the borrow shown under the table is 0.

The first example shows what an adder circuit will have to do: a carry produced in one column is used by the next. The second shows why subtraction is awkward to build this way. A borrow can run through a string of 0 columns, and the rule for a column is different from the addition rule. Section 4.3 replaces subtraction by an addition so that the same adder serves both.

The half adder

Section 1.1 met the smallest adder. It adds two bits $a$ and $b$ and produces two outputs: a sum bit $s$ and a carry bit $c$.

Truth table with 2 inputs (a, b) and outputs c, s; 4 rows in ascending binary order, a most significant

a	b	c	s
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	0

The sum is 1 when exactly one input is 1, which is the exclusive OR $a \oplus b$, and the carry is 1 only when both are, which is $ab$. (The schematic is in Figure 1.1.1.)

A half adder is enough for the rightmost column, where no carry arrives. It is not enough for any other column, because it has no input for the carry from the right. That is the missing half.

The full adder

Definition 4.1.2(full adder).

A full adder adds three one-bit numbers: the two bits $a$ and $b$ of its column and a carry in $\mathit{cin}$ from the column on its right. It has two outputs: the sum bit $s$ and the carry out $\mathit{cout}$ to the column on its left. Its outputs are the two bits of the sum of its inputs, so $s$ is the low bit and $\mathit{cout}$ is the high bit.

The table lists both outputs for all eight input rows. The first-listed input is the most significant bit of a row, as everywhere in this book, so the carry in comes first.

Truth table with 3 inputs (cin, a, b) and outputs cout, s; 8 rows in ascending binary order, cin most significant

$\mathrm{cin}$	a	b	$\mathrm{cout}$	s
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	0	1
1	0	1	1	0
1	1	0	1	0
1	1	1	1	1

The sum column is 1 on the rows where an odd number of inputs are 1, which is the three-way exclusive OR $\mathrm{cin} \oplus a \oplus b$. The carry-out column is 1 on the rows where at least two inputs are 1: the majority of the three, $ab + a \cdot \mathrm{cin} + b \cdot \mathrm{cin}$. Both columns follow from the definition: the pair of outputs is the binary sum of the three input bits.

There is a second way to write the carry. A carry happens when both bits are 1, or when exactly one of them is 1 and the carry in arrives. That is the half adder's carry, $ab$, together with the half adder's sum bit AND the carry in:

$ab +$ $a \cdot \mathrm{cin} +$ $b \cdot \mathrm{cin}$ $= ab +$ $\mathrm{cin} \cdot (a \oplus b)$

The two forms are equal on every row, and the second is the one that gives a short circuit: two half adders and an OR gate. The first half adder adds $a$ and $b$. The second adds that sum bit and the carry in. Either half adder may produce a carry, but never both at once, so an OR gate combines them.

A logic schematic with inputs a, b and cin and outputs s and cout.

XOR gate x1: inputs a and b; output n1.

AND gate g1: inputs b and a; output n2.

XOR gate x2: inputs n1 and cin; output s.

AND gate g2: inputs n1 and cin; output n3.

OR gate o1: inputs n3 and n2; output cout.

It agrees with the function logic:ch04/full-adder#s,cout.

Description: A circuit with inputs a, b and cin and outputs s and cout. An XOR gate and an AND gate both take a and b. A second XOR gate takes the output of the first XOR gate and cin, and gives s. A second AND gate takes the output of the first XOR gate and cin. An OR gate takes the outputs of the two AND gates and gives cout.

Figure 4.1.1. A full adder as two half adders and an OR gate. The checked drawing computes the two outputs of the table above.

The first XOR and first AND gate in Figure 4.1.1 are the half adder of Section 1.1 with its two inputs wired to $a$ and $b$. The second XOR and second AND gate are another half adder, and its inputs are the first one's sum bit and $\mathit{cin}$.

Chaining adders

Definition 4.1.3(ripple-carry adder).

A ripple-carry adder adds two $n$-bit numbers with $n$ full adders in a row. Each adder handles one column: its inputs are that column's two bits and the carry out of the column to its right, and its sum bit is that column's bit of the result. The carry in of the rightmost adder is 0 for a plain addition, and the carry out of the leftmost adder is the carry out of the whole addition.

Illustration a block diagram that explains an idea; its behavior is not checked

A block diagram with inputs b0, a0, b1, a1 and cin and outputs s0, s1 and cout.

Block "full adder" fa0: a is a0, b is b0, cin is cin, s is s0, cout is n1.

Block "full adder" fa1: a is a1, b is b1, cin is n1, s is s1, cout is cout.

This diagram is illustrative: its behavior is not checked.

Description: Two boxes labeled full adder in a row, for bit 0 on the left and bit 1 on the right. Each box has inputs a, b and cin and outputs s and cout. Each box takes its own bit of a and b from above and gives its sum bit upward. The cout of the first box is wired to the cin of the second, labeled c1. A cin enters the first box from the left and a cout leaves the second box on the right.

Figure 4.1.2. Two full adders in a row, the start of a longer chain. The carry out of bit 0 is the carry in of bit 1, so the carry moves from left to right here, with bit 0 on the left.

The drawing stops at two stages; a wider adder repeats the stage. It shows bit 0 on the left, so the carry runs left to right. A written number has its bit 0 on the right, and many drawings put the stages that way, with the carry running right to left. The two layouts are the same circuit.

Why is it called ripple carry? A column's sum bit depends on its carry in, and that carry in depends on the column before it. When a carry is produced in column 0 it may have to pass through every later column before the top sum bit is right. Take four bits:

4-bit A + B: A is 0111, B is 0001; result 1000, 8 unsigned, -8 signed; carry 0

	4-bit pattern	unsigned
A	0111	7
+ B	0001	1
=	1000	8

carry = 0

Here column 0 adds 1 and 1, so it carries; columns 1 and 2 each add a 1, a 0 and the carry, so each writes 0 and carries again; column 3 adds 0, 0 and the carry and writes 1. The carry made in column 0 passed through columns 1 and 2 and was used up in column 3, so the top sum bit was settled only after it arrived. A longer chain has a longer worst case. Chapter 6 (not written yet) puts numbers on delays like this one, and Section 4.2 writes the same chain in SystemVerilog.

Two 8-bit numbers are added by a ripple-carry adder. For which of these additions can the carry out of column 0 affect the top sum bit? Only when every column in between passes a carry on, as in 01111111 plus 00000001. Never: a carry affects only the column to its left. Always: every addition sends its carry through all eight columns.

Course conventions

How CSE 369 writes this

Lecture 4 names the carry into column $i$ as $c_i$ and the carry out of it as $c_{i+1}$, and writes a full adder's sum as the exclusive OR of its three inputs and its carry out as their majority.^{F (fact ch04/adder-notation)} This book uses $\mathit{cin}$ and $\mathit{cout}$ for the two ends of one adder and keeps $c_1$, $c_2$ and the like for the wires between stages in a chain. Bits of a number are numbered from 0 at the right, and a column is named by its bit number.

Pitfalls

Common pitfall

• Forgetting the carry in. A half adder is correct only for the rightmost column; any other column needs a full adder, or the carry from the right is lost.
• Writing the carry bit as the XOR of the inputs. The sum bit is the exclusive OR and the carry bit is the majority; they are different columns of the table.
• Dropping the carry out of the top column. An $n$-bit sum can need $n+1$ bits, and the carry out is that extra bit.
• Subtracting by borrowing as if it were a carry. A borrow passes from a column to the column on its left, as a carry does, but the rule for a column is different; Section 4.3 turns subtraction into addition so the carry rule is the only one needed.
• Believing a carry moves only one column. A column that holds exactly one 1 passes a carry on, so a carry can run through many columns.

Check your understanding

Take the quiz (5 questions)

How many whole numbers can an 8-bit unsigned pattern represent, counting 0?

256255128

Which expression is the carry out of a full adder?

$ab + a \cdot \mathrm{cin} + b \cdot \mathrm{cin}$$a \oplus b \oplus \mathrm{cin}$$a \cdot b \cdot \mathrm{cin}$

On how many of the eight rows of the full adder table is the carry out 1?

432

Adding 63 and 8 as 8-bit unsigned numbers, what is the carry out of the top column?

01

Subtracting 8 from 65 as 8-bit unsigned numbers, is any borrow needed from beyond the top column?

01

Exercises

Exercise 4.1.1

Add the 8-bit unsigned numbers 00101101 and 00011011 by hand. For each column from 0 to 7, write the carry out of that column. Then give the result and say whether any carry leaves the top column.

Hint

Work from the right and carry the 1 from a column into the next. A column holding two 1s writes 0 and carries; a column holding three 1s (two bits and a carry) writes 1 and carries.

Solution

Column by column, from column 0 at the right:

• Column 0: 1 and 1 with no carry in make two. Write 0, carry 1.
• Column 1: 0 and 1 and the carry make two. Write 0, carry 1.
• Column 2: 1 and 0 and the carry make two. Write 0, carry 1.
• Column 3: 1 and 1 and the carry make three. Write 1, carry 1.
• Column 4: 0 and 1 and the carry make two. Write 0, carry 1.
• Column 5: 1 and 0 and the carry make two. Write 0, carry 1.
• Column 6: 0 and 0 and the carry make one. Write 1, carry 0.
• Column 7: 0 and 0 and no carry make zero. Write 0, carry 0.

8-bit A + B: A is 00101101, B is 00011011; result 01001000, 72 unsigned, 72 signed; carry 0

	8-bit pattern	unsigned
A	00101101	45
+ B	00011011	27
=	01001000	72

carry = 0

The result row agrees with the columns, and the carry out of the top column is 0.

Tags: Warm-upArithmeticNumber representation

Exercise 4.1.2

Subtract 00000001 from 10010000 as 8-bit unsigned numbers, by borrowing. Which columns borrow, and where does the borrow come from?

Hint

Column 0 has to take away a 1 from a 0. Look to the left for the first column that has a 1 to lend.

Solution

Column 0 holds a 0 and must take away a 1, so it borrows. Columns 1, 2 and 3 are also 0, so each of them borrows from the column to its left in turn, and the chain stops at column 4, which holds a 1 to lend. Column 4 gives up its 1 and becomes 0. Columns 3, 2 and 1 each receive a 2, pass one on and keep 1. Column 0 receives a 2, takes away the 1 and keeps 1.

8-bit A − B: A is 10010000, B is 00000001; result 10001111, 143 unsigned, -113 signed; borrow 0

	8-bit pattern	unsigned
A	10010000	144
− B	00000001	1
=	10001111	143

borrow = 0

The result row has 1s in columns 0 to 3 and in column 7, and the borrow out of the top column is 0, because the first number is larger than the second.

Tags: Warm-upArithmeticNumber representation

Exercise 4.1.3

The carry out of a full adder is 1 when at least two of its three inputs are 1. Write it as a sum of three products, then write the version that uses the sum bit of a half adder, and show that both forms agree on every row.

Hint

Two inputs equal to 1 can be any pair: $a$ and $b$, $a$ and $\mathit{cin}$, or $b$ and $\mathit{cin}$. For the second form, ask when exactly one of $a$ and $b$ is 1.

Solution

At least two inputs are 1 when some pair of inputs are both 1. There are three pairs, so the carry out is the sum of the three products of a pair:

$ab + a \cdot \mathrm{cin} + b \cdot \mathrm{cin}$

The other form separates the cases by whether $a$ and $b$ are both 1. If they are, a carry happens whatever the carry in is: the term $ab$. If exactly one of them is 1, a carry happens only when the carry in is 1, and "exactly one of $a$ and $b$ is 1" is $a \oplus b$. Together:

$ab +$ $a \cdot \mathrm{cin} +$ $b \cdot \mathrm{cin}$ $= ab +$ $\mathrm{cin} \cdot (a \oplus b)$

The equivalence check compares the two sides on every input row of the full adder, so they agree on all eight.

Tags: StandardArithmeticBoolean algebra

Exercise 4.1.4

In a ripple-carry adder for 8-bit numbers, add 01111111 and 00000001. Through how many columns does the carry produced in column 0 keep going, and what are the result and the carry out?

Hint

A column carries on when it holds two 1s, or a 1 and the incoming carry.

Solution

Column 0 adds 1 and 1 and carries. Columns 1 to 6 each hold a 1 and a 0 and receive that carry, so each writes 0 and carries again. Column 7 holds 0 and 0 and the carry, writes 1, and carries nothing. The carry produced in column 0 therefore passes through columns 1 to 6, six more columns, and is absorbed by column 7.

8-bit A + B: A is 01111111, B is 00000001; result 10000000, 128 unsigned, -128 signed; carry 0

	8-bit pattern	unsigned
A	01111111	127
+ B	00000001	1
=	10000000	128

carry = 0

The result is 10000000 and no carry leaves the top column. The top sum bit of this addition depends on a carry that started at the bottom, which is the worst case for a ripple-carry adder.

Tags: StandardArithmetic

Exercise 4.1.5

Two 8-bit unsigned numbers are added. How many bits does the sum need, in the worst case? Show an addition that needs all of them.

Hint

The sum is largest when both numbers are largest. The carry out of the top column is the extra bit.

Solution

Each number is at most $2^8-1$, so the sum is at most $2^9-2$, which needs 9 bits but not 10. The largest pair is the one in which every bit is 1:

8-bit A + B: A is 11111111, B is 11111111; result 11111110, 254 unsigned, -2 signed; carry 1

	8-bit pattern	unsigned
A	11111111	255
+ B	11111111	255
=	11111110	254

carry = 1

The eight result bits are 11111110 and the carry out is 1. The carry out is the ninth, most significant bit of the sum, so the complete sum is the nine bits 1 1111 1110. An 8-bit result alone would be a wrong answer here.

Tags: ChallengeArithmeticNumber representation