Learn › Topic 7

Binary adders: half adder, full adder and ripple-carry adder

8 min read · bitGateLab Team

Addition is the most important operation in a computer: it is used to subtract, to multiply, to compute memory addresses and to count events. Here you will build an adder from scratch: first the one-bit half adder, then the full adder that accepts a carry, then the multi-bit ripple-carry adder and, finally, how the same circuit subtracts using 2's complement.

Adding in binary by hand

There are four rules for adding two bits: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1 and 1 + 1 = 10₂, that is, 0 with a carry of 1 into the next column. If a carry also comes in, 1 + 1 + 1 = 11₂: result 1 and carry 1. Just as in decimal, you add column by column from right to left, passing the carry to the left.

Half adder

The half adder adds two bits, A and B, and produces two outputs: the sum S and the carry C.

The S column is the table of an XOR and the C column is that of an AND. Therefore:

S = A ⊕ B    C = AB

It is called a "half" adder because it has no input for the carry coming from a previous column, so it is only good for the least significant bit.

Full adder

The full adder adds three bits: A, B and the carry-in C_in. It produces the sum S and the carry-out C_out. Notice that the pair (C_out, S) is, in binary, the number of ones present at the inputs.

S is 1 when there is an odd number of ones: S = Σm(1, 2, 4, 7) = A ⊕ B ⊕ C_in. C_out is 1 when there are two or more ones: C_out = Σm(3, 5, 6, 7), which simplifies to the majority function:

C_out = AB + AC_in + BC_in

If you try to form groups on the Karnaugh map of S, you will see that no 1 has a neighbor holding a 1: it is the checkerboard pattern typical of XOR, which cannot be simplified as a sum of products.

Full adder from two half adders

A practical way to build it is to chain two half adders and an OR:

1. First half adder: P = A ⊕ B and G = AB.
2. Second half adder, with P and C_in: S = P ⊕ C_in and a partial carry P·C_in.
3. C_out = G + P·C_in = AB + (A ⊕ B)C_in.

This expression is equivalent to the majority one: if A and B are both 1, AB already produces the carry; if exactly one of them is 1, the carry depends on C_in. G is called the generate signal and P the propagate signal.

Ripple-carry adder

To add n-bit numbers, n full adders are connected in a row: the C_out of each stage goes in as the C_in of the next. The C_in of the first stage is set to 0, and the C_out of the last one is the final carry. This structure is called a ripple-carry adder, or simply ripple carry, because the carry "ripples" from stage to stage like a wave. In the 74HC family there is a chip that contains four full adders already connected this way (the 74HC283).

The price is time. Stage 3 cannot give its final result until the carry from stage 2 arrives, which in turn waits for the one from stage 1. If each stage takes two gate levels to produce its carry, an n-bit adder takes on the order of 2n gate delays in the worst case. For 64 bits that is too slow, which is why processors use carry-lookahead adders, which compute the carries in parallel from the G and P signals. In the simulator's timing diagram you can watch the outputs change in steps until they settle.

Subtracting with the same adder

As explained in number systems, in 2's complement the negative of B is B + 1. Therefore:

A − B = A + B + 1

To get this, all you need is an XOR on each bit of B, with its other input connected to a control line M, and M also connected to the C_in of the first stage. With M = 0 the XOR gates pass B through and C_in = 0: the circuit adds. With M = 1 the XOR gates invert B and C_in = 1 supplies the "+1": the circuit subtracts.

Common mistakes

• Using a half adder in the intermediate stages. Every stage that receives a carry needs a full adder.
• Leaving the C_in of the first stage floating. It must go to 0 to add, or to M in an adder-subtractor.
• Confusing the final carry with overflow. In signed numbers the final carry is discarded; overflow is detected with C₃ ⊕ C₄.
• Forgetting the "+1" when subtracting and connecting only the inverters: the result comes out one unit too low.
• Writing S = A + B + C_in with OR. A one-bit sum is an XOR, not an OR.

Try it in the simulator

Building an adder in the editor is the best bridge between gates and arithmetic. Start with one bit and grow to four.

1. Place two inputs, an XOR and an AND, and wire them as in the half adder diagram. Generate its truth table.
2. Build a full adder from two half adders and an OR, and check its 8 rows against the table in this article.
3. Copy the full adder four times and chain the carries. Set the first C_in to 0.
4. Set the inputs to 1011 and 0110 and check that the output is 0001 with a final carry of 1.
5. Open the timing diagram, change an input that forces the carry to travel through all four stages (for example 1111 + 0001) and watch how the outputs settle.

Exercises

1. Compute S and C_out of a full adder with A = 1, B = 0, C_in = 1.
   Answer

   There are two ones: S = 0 and C_out = 1 (1 + 0 + 1 = 10₂).

2. Add 0111 + 0101 with a 4-bit adder and give the carries of each stage.
   Answer

   Stage 0: 1 + 1 = 0, carry 1. Stage 1: 1 + 0 + 1 = 0, carry 1. Stage 2: 1 + 1 + 1 = 1, carry 1. Stage 3: 0 + 0 + 1 = 1, carry 0. Result 1100 = 12 (7 + 5).

3. With a 4-bit adder-subtractor compute 6 − 3 and state the value of M.
   Answer

   M = 1. 0110 + 1100 + 1 = 1 0011. The carry is discarded: 0011 = 3.

4. Reading them as 4-bit signed numbers, is there overflow in 0111 + 0101?
   Answer

   Yes. 7 + 5 = 12 does not fit in the range −8 to +7. The result 1100 would be read as −4. The carries are C₃ = 1 and C₄ = 0, and V = 1 ⊕ 0 = 1.