on

# 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 |
---|---|---|

0 | 0 | 00 |

0 | 1 | 01 |

1 | 0 | 01 |

1 | 1 | 10 |

This table represents all of the values that `a + b`

take for all possible combinations of `a`

and `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:

a | b | carry | sum |
---|---|---|---|

0 | 0 | 0 | 0 |

0 | 1 | 0 | 1 |

1 | 0 | 0 | 1 |

1 | 1 | 1 | 0 |

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 |
---|---|---|---|

F | F | F | F |

F | T | F | T |

T | F | F | T |

T | T | T | F |

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 `a`

and `b`

it computes `sum`

and `carry`

.

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`

and `b1`

:

a1 | b1 | c0 | a1 + b1 | c1 | s1 |
---|---|---|---|---|---|

0 | 0 | 0 | 00 | 0 | 0 |

0 | 0 | 1 | 01 | 0 | 1 |

0 | 1 | 0 | 01 | 0 | 1 |

0 | 1 | 1 | 10 | 1 | 0 |

1 | 0 | 0 | 01 | 0 | 1 |

1 | 0 | 1 | 10 | 1 | 0 |

1 | 1 | 0 | 10 | 1 | 0 |

1 | 1 | 1 | 11 | 1 | 1 |

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.