The half adder and the full adder

Adding two bits

How does a circuit perform an addition? Let's start with the simplest case: adding two bits A and B. The result fits in two digits, a sum S and a carry C. In binary: 0+0=00, 0+1=01, 1+0=01, 1+1=10. Looking at these cases, you notice that the sum S is exactly the XOR of A and B, and the carry C is exactly the AND of A and B.

The half adder

Half adder:

   A ---+----[ XOR ]---- S   (sum = A XOR B)
        |   /
   B ---+--/
        |  \
        +---[ AND ]---- C   (carry = A AND B)

check:  1 + 1 -> S = (1 XOR 1) = 0,  C = (1 AND 1) = 1  -> binary result 10 (= 2)

This circuit is called a half adder because it lacks one thing: it cannot take into account an incoming carry, coming from the addition of the previous bit.

The full adder

To add numbers of several bits, each stage must accept three inputs: A, B, and the incoming carry C_in. This is the full adder. It is obtained by combining two half adders and an OR gate.

Full adder, column by column (adding 1011 + 0110):

  carry   : 1 1 1 0
            1 0 1 1
          + 0 1 1 0
          ---------
          1 0 0 0 1     (each column: A + B + incoming carry)

(each column produces a sum bit and a carry to the column on its left)

By chaining n full adders, with each one's carry-out feeding the next one's carry-in, numbers of n bits can be added.

Classic pitfall

With a half adder alone, you can only add in the very first column (the rightmost one), where there is no incoming carry yet. All the following columns require a full adder: forgetting the incoming carry is the classic mistake that gives a wrong result as soon as a carry appears.