Binary Adder Circuit

Before we build any circuits, let's review how binary addition works at the bit level. Adding two single bits follows four simple rules:

0 + 0 = 0, carry 0
0 + 1 = 1, carry 0
1 + 0 = 1, carry 0
1 + 1 = 0, carry 1   (since binary 1 + 1 = 10)

Notice there are two outputs: a sum bit and a carry bit. The sum bit is 1 when the inputs are different — that's exactly the XOR function. The carry bit is 1 only when both inputs are 1 — that's the AND function. This observation is the entire foundation of the half adder.

The half adder is the simplest circuit that adds two binary digits. It takes two inputs, A and B, and produces two outputs: Sum (S) and Carry (C).

Circuit: The half adder consists of exactly two logic gates:

• An XOR gate that computes the sum: S = A ⊕ B
• An AND gate that computes the carry: C = A · B

Truth table:

A | B | C | S
0 | 0 | 0 | 0
0 | 1 | 0 | 1
1 | 0 | 0 | 1
1 | 1 | 1 | 0

The "half" in half adder comes from its limitation: it can't accept a carry input from a previous lower-order bit. That's why it only works for the least significant bit (the rightmost bit) of a multi-bit addition, where there's no incoming carry.

The full adder extends the half adder by adding a third input: Carry In (Cin). This allows it to handle carries propagating from lower bits. A full adder has three inputs (A, B, Cin) and two outputs (Sum, Carry Out).

Circuit: A full adder is built from two half adders and one OR gate:

1. The first half adder computes S1 = A ⊕ B and C1 = A · B
2. The second half adder computes Sum = S1 ⊕ Cin and C2 = S1 · Cin
3. The final carry out is Cout = C1 + C2 (OR gate)

Truth table:

A | B | Cin | Cout | S
0 | 0 |  0  |  0   | 0
0 | 0 |  1  |  0   | 1
0 | 1 |  0  |  0   | 1
0 | 1 |  1  |  1   | 0
1 | 0 |  0  |  0   | 1
1 | 0 |  1  |  1   | 0
1 | 1 |  0  |  1   | 0
1 | 1 |  1  |  1   | 1

A full adder uses 5 logic gates total: 2 XOR, 2 AND, and 1 OR. That's about 30 transistors in a standard CMOS implementation.

To add multi-bit binary numbers (like two 8-bit or 32-bit values), we chain full adders together. This arrangement is called a ripple-carry adder because the carry signal propagates (or "ripples") through each stage.

How it works:

1. Bit 0 (LSB): A half adder handles the least significant bits (no incoming carry).
2. Bit 1: A full adder takes A1, B1, and the carry out from bit 0.
3. Bit 2 through N-1: Each subsequent full adder takes the carry out from the previous stage.
4. Bit N (final): The carry out from the highest bit becomes the overflow flag.

Example: Adding binary 1011 (11) and 0111 (7):

   Carry: 1 1 1 0
   A:     1 0 1 1
   B:     0 1 1 1
   -----------------
   Sum:   0 0 1 0
   Final Carry: 1 (result = 10010 = 18)

For an N-bit ripple-carry adder, the total gate delay is N times the delay of one full adder. This is the main drawback: adding wider numbers takes proportionally longer because each carry must be computed sequentially.

Because ripple-carry adders get slower with wider word sizes, modern CPUs use a carry-lookahead adder (CLA). The CLA precomputes the carry for each bit position using two intermediate signals:

• Generate (G): G = A · B — this bit position generates a carry regardless of the incoming carry.
• Propagate (P): P = A + B (or A ⊕ B) — this bit position propagates an incoming carry through.

With G and P, the carry for any position can be computed in parallel rather than sequentially. For example, C3 = G3 + P3·G2 + P3·P2·G1 + P3·P2·P1·G0 + P3·P2·P1·P0·Cin. This expression gets large for wider adders, so CLA adders typically group bits into 4-bit blocks and cascade the lookahead logic hierarchically.

The same adder hardware can handle subtraction using two's complement. To compute A - B, the ALU inverts all bits of B and adds 1 (using the carry-in of the LSB full adder), then performs standard addition. This means one adder circuit handles both addition and subtraction with minimal extra logic.

An increment-by-1 circuit is even simpler: it's just an adder with one input set to 1 and the other fed the value to increment. Dedicated incrementers are used in program counters and loop counters throughout the CPU.

• Binary addition in hardware starts with the observation that Sum = XOR and Carry = AND.
• A half adder (XOR + AND) handles single-bit addition without carry input.
• A full adder (two half adders + an OR gate) adds three bits, including a carry in.
• Ripple-carry adders chain full adders but suffer from sequential carry propagation delay.
• Carry-lookahead adders precompute carries in parallel and are used in all modern CPUs.
• The same adder hardware does subtraction via two's complement inversion.