2.2 Full adder

A half adder is not sufficient to be the adder of a bit. Let x_i represent the value of bit i of a number x, y_i represent the value of bit i of a number y. Let s = x + y, and s_i represents the value of bit i of the sum.

The carry bit from the addition of bit position i is represented as c_i. This is an intermediate term that helps the explanation of a full adder.

Using the result and carry functions, ∀i ∈ [1…n − 1] : s_i = R(R(x_i,y_i),c_i−1) in which n is the number of bits. s₀ = R(x₀,y₀) because there is no previous digit. At the same time, we can also express c_i using the function ‘C’: ∀i ∈ [1…n − 1] : c_i = C(x_i,y_i) + C(R(x_i,y_i),c_i−1). c₀ = C(x₀,y₀) because there is no carry from a previous digit.

Note how we use two ‘R’ and two ‘C’ to compute the bit of a sum and its corresponding carry. This means we need two half adder circuits to do this.