A Machine That Can Add
On the 4th year of college I ran into one of the most beautiful things I had ever seen: the adder.
I remember having a hard time containing the enthusiasm: you'd think that computing sums was something reserved for higher order intelligence, so it was mesmerizing seeing it in action by a machine.
In a base-2 adder (i.e. one that operates over binary numbers), you can enumerate all of the possible sums for single digit numbers. For example:
|a||b||a + b|
This table represents all of the values that
a + b take for all possible combinations of
b (e.g. when
0 + 0 = 0 and
0 + 1 = 1). Notably,
1 + 1 = 10 (
1 + 1 = 2 in decimal), which needs two bits to be represented. We'll call that extra bit the carry. For example:
It is easy to verify that the following logical expression leads to the same results of addition:
- sum = a xor b
- carry = a and b
With the following truth table:
|a||b||c = a && b||s = a xor b|
Interestingly, a circuit can be built using logical gates that can perform these logical operations:
That gives you the ability to add two single-digit numbers: given
b it computes
To add numbers with two digits, we take the carry
c0 value that was computed in the first digit and combine that with the second digits
|a1||b1||c0||a1 + b1||c1||s1|
Which, can be built as the following digital circuit, which is known as the full adder:
The full adder is pretty awesome, because if you keep chaining the carry bits with the next digits to be added, you can sum arbitrarily long binary numbers:
This is a circuit that is capable of computing the sum of two binary numbers.
A machine that can add.