Binary arithmetic is a combinatorial problem. It may seem trivial to
use the methods we have already seen for designing
combinatorial circuits to obtain circuits for binary arithmetic.
However, there is a problem. It turns out that the normal way of
creating such circuits would often use up way too many gates. We
must search for different ways.
For binary integer addition, we can sacrifice our requirement on
circuit depth that we previously had, in order to use fewer
gates. The resulting circuit is of a type that we call iterative
combinatorial circuit, in that it contains several copies of a
simple element. For binary addition, that simple element is called a
full adder.
A full adder is a combinatorial circuit (or actually two
combinatorial circuits) of three inputs and two outputs. Its
function is to add two binary digits plus a carry from the previous
position, and give a twobit result, the normal output and the carry
to the next position. Here is the truth table for a full adder:
x y cin  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
Here, we have used variable names x and y for
the inputs, cin for the carryin, s for the sum
output and cout for the carryout.
A full adder can be trivially built using our ordinary design
methods for combinatorial circuits. Here is the resulting circuit
diagram:
The next step is to combine a series of such full adders into a
circuit that can add (say) two 8bit positive numbers. We do this by
connecting the carryout from one full adder to the carryin of the
full adder immediately to its left. The rightmost full adder takes a
0 on its carryin.
Here, we have used subscript i for the ith
binary position.
As you can see, the depth of this circuit is no longer two, but
considerably larger. In fact, the output and carry from position
7 is determined in part by the inputs of position
0. The signal must traverse all the full adders, with a
corresponding delay as a result.
There are intermediate solutions between the two extreme ones we
have seen so far (i.e. a combinatorial circuit for the entire (say)
32bit adder, and an iterative combinatorial circuit whose elements
are onebit adders built as ordinary combinatorial circuits). We can
for instance build an 8bit adder as an ordinary twolevel
combinatorial circuit and build a 32bit adder from four such 8bit
adders. An 8bit adder can trivially be build from 65536
(2^{16}) andgates, and a giant
65536input orgate.
Another intermediate solution consists of building socalled
carryaccelerator circuits. [To be completed...]
Our binary adder can already handle negative numbers as indicated
in the section on binary arithmetic. But we have not discussed how we can get it
to handle subtraction.
To see how this can be done, notice that in order to compute the
expression x  y, we can compute the expression x + y
instead. We know from the section on binary arithmetic how to negate a number by inverting all the
bits and adding 1. Thus, we can compute the expression
as x + inv(y) + 1. It suffices to invert all the inputs of
the second operand before they reach the adder, but how do we add
the 1. That seems to require another adder just for
that. Luckily, we have an unused carryin signal to position 0
that we can use. Giving a 1 on this input in effect
adds one to the result. The complete circuit with addition and
subtraction looks like this:
Binary multiplication is even harder than binary addition. There
is no good iterative combinatorial circuit available, so we have to
use even heavier artillery. The solution is going to be to use a
sequential circuit that computes one addition for every clock pulse.
We will discuss this more in a later section since it needs
mechanisms we have not discussed yet.
