2.5 Addition, logically

We can put these logic gates together to do addition using binary arithmetic, as we discussed in section 2.2: algorithm$addition

Focus on the values after the equal signs, and temporarily forget the carrying in the last case. The results are the same as what xor does with two inputs:

We lost the carry bit but limited ourselves to having only one output bit. What gate operation would give us that 1 carry bit only if both inputs were also 1 and otherwise return 0? Correct, it’s and! If we combine the xor and the and, and give ourselves two bits of output, we can do a simple addition of two bits.

Exercise 2.6

Try drawing a circuit that would do this before peeking at what follows. You are allowed to clone the value of a bit and send it to two different gates.

The circuit is

where A, B, S, and C are bits. The circuit takes two single input...