0 | 0 | 1 | 1 |

+ 0 | + 1 | + 0 | + 1 |

00 | 01 | 01 | 10 |

input | output | ||
---|---|---|---|

A | B | carry | sum |

0 | 0 | 0 | 0 |

0 | 1 | 0 | 1 |

1 | 0 | 0 | 1 |

1 | 1 | 1 | 0 |

## What do these results look like?

input | output | ||
---|---|---|---|

A | B | carry | sum |

0 | 0 | 0 | 0 |

0 | 1 | 0 | 1 |

1 | 0 | 0 | 1 |

1 | 1 | 1 | 0 |

sum = A XOR B

carry = A AND B

We can also draw this using the other XOR circuit diagram or an XOR gate.NOTE: This does not allow for a carry-in! What about if we want to add numbers that have more than one bit?

This does only half of the total task, and is known as a half-adder.

0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | |

+ 0 | + 1 | + 0 | + 1 | + 0 | + 1 | + 0 | + 1 | |

00 | 01 | 01 | 10 | 00 | 01 | 01 | 10 | |

carry-in | + 0 | + 0 | + 0 | + 0 | + 1 | + 1 | + 1 | + 1 |

00 | 01 | 01 | 10 | 01 | 10 | 10 | 11 |

input | intermediate | output | ||||
---|---|---|---|---|---|---|

carry_{in} |
A | B | carry_{h1} | sum_{h1} |
carry_{out} | sum_{full} |

0 | 0 | 0 | 0 | 0 | 0 | 0 |

0 | 0 | 1 | 0 | 1 | 0 | 1 |

0 | 1 | 0 | 0 | 1 | 0 | 1 |

0 | 1 | 1 | 1 | 0 | 1 | 0 |

1 | 0 | 0 | 0 | 0 | 0 | 1 |

1 | 0 | 1 | 0 | 1 | 1 | 0 |

1 | 1 | 0 | 0 | 1 | 1 | 0 |

1 | 1 | 1 | 1 | 0 | 1 | 1 |

If we show the first bit of the second addition (carry_{in}+ sum_{h1}) explicitly, notice the relationship between sum_{h2}and sum_{full}.

input | intermediate | output | ||||||
---|---|---|---|---|---|---|---|---|

carry_{in} |
A | B | carry_{h1} | sum_{h1} |
carry_{h2} | sum_{h2} |
carry_{out} | sum_{full} |

0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |

0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |

0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 |

1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 |

1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |

1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 |

1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 |

sum_{full}= carry_{in}XOR sum_{h1}

(which makes sense because we did another one-bit half-add: carry_{in}+ sum_{h1})

What about the carry? Notice the relationship between carry_{h1}, carry_{h2}, and carry_{out}.

input | intermediate | output | ||||||
---|---|---|---|---|---|---|---|---|

carry_{in} |
A | B | carry_{h1} | sum_{h1} |
carry_{h2} | sum_{h2} |
carry_{out} | sum_{full} |

0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |

0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |

0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 |

1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 |

1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |

1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 |

1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 |

carry_{out}= carry_{h1}OR carry_{h2}

We have two half-adders. The first adds A + B.
The sum bit of that is then
added to the carry_{in} in the second half-adder. The overall
sum is the sum bit from the second add.

sum_{full}= carry_{in}XOR sum_{h1}

The addition yields a carry if either of the two half-adders yield a carry.

carry_{out}= carry_{h1}OR carry_{h2}

Next: How do we set up a multi-bit adder?

Alyce Brady, Kalamazoo College