The adder is the most basic computational element of a computer. All other arithmetic computations are based on adding. Subtraction, for example, is accomplished by adding two properly formatted numbers (two's complement being a common format), while multiplication and division are implemented as repeated additions and subtractions, respectively. If the central processing unit (CPU) is the heart of the computer, the adder is the heart of the CPU.

Computer hardware works with binary numbers, which are strings of single binary digits (bits, 1s and 0s). To build a binary adder of any size it is sufficient to build a unit which can add two single bits--and this is not difficult, for in single-bit addition there are only three calculations that can be performed:

• 0 + 0 = 0
•  
• 0 + 1 = 0
•  
• 1 + 1 = 10

In the third case we encounter a slight complication: A single bit of output does not suffice to represent the sum...