15.4 Adders and subtractors

Adders and subtractors are the building blocks that let digital circuits do math. They handle binary addition and subtraction, starting from simple single-bit operations and scaling up to multi-bit arithmetic used in real processors.

Understanding how these circuits work gives you a clear picture of how computers process numbers at the hardware level, and why design choices like carry propagation matter for speed.

Adders

Half Adder and Full Adder

A half adder adds two single-bit binary numbers ($A$ and $B$) and produces two outputs: a sum ($S$) and a carry out ($C$). It uses an XOR gate for the sum and an AND gate for the carry.

The Boolean expressions are:

• $S = A \oplus B$
• $C = A \cdot B$

Think of it this way: the XOR tells you the single-bit result, and the AND tells you whether the addition "overflowed" into the next column (just like carrying a 1 in decimal addition).

The limitation of a half adder is that it has no input for a carry from a previous stage. That's where the full adder comes in.

A full adder adds three single-bit inputs: $A$, $B$, and a carry in ($C_{in}$). It produces a sum ($S$) and a carry out ($C_{out}$). Internally, you can build one from two half adders and an OR gate:

1. The first half adder computes $A \oplus B$ and $A \cdot B$.
2. The second half adder adds $C_{in}$ to the result of the first XOR.
3. The OR gate combines the two carry outputs to produce $C_{out}$.

The Boolean expressions are:

• $S = A \oplus B \oplus C_{in}$
• $C_{out} = (A \cdot B) + (C_{in} \cdot (A \oplus B))$

Multi-bit Adders

To add numbers wider than one bit, you chain full adders together.

A ripple carry adder (RCA) is the simplest approach. You cascade $n$ full adders for an $n$-bit addition, connecting the $C_{out}$ of each stage to the $C_{in}$ of the next. For example, a 4-bit RCA uses four full adders in series.

The downside is speed. Each full adder has to wait for the carry from the previous stage before it can produce a valid output. The total delay grows linearly with the number of bits, so a 32-bit RCA is roughly 32 times slower than a single full adder. This is called carry propagation delay.

A carry look-ahead adder (CLA) solves this problem by computing carry signals in parallel rather than waiting for them to ripple through. It uses two intermediate signals for each bit position:

• Generate ($G_i = A_i \cdot B_i$): a carry is produced at this stage regardless of the incoming carry.
• Propagate ($P_i = A_i \oplus B_i$): an incoming carry will pass through this stage.

Using these signals, the CLA calculates all carry bits simultaneously with dedicated logic. For instance, $C_1 = G_0 + P_0 \cdot C_0$ and $C_2 = G_1 + P_1 \cdot G_0 + P_1 \cdot P_0 \cdot C_0$, and so on. This is significantly faster than an RCA, but the trade-off is more complex hardware and more gates.

Subtractors

Half Subtractor and Full Subtractor

A half subtractor subtracts one single-bit number ($B$) from another ($A$). It produces a difference ($D$) and a borrow out ($B_{out}$).

• $D = A \oplus B$ (same XOR as the half adder)
• $B_{out} = \overline{A} \cdot B$ (an AND gate with $A$ inverted)

The borrow output is 1 when $A = 0$ and $B = 1$, because you need to "borrow" from the next column, just like borrowing in decimal subtraction.

A full subtractor handles three inputs: $A$, $B$, and a borrow in ($B_{in}$) from a previous stage. It's built from two half subtractors and an OR gate, similar to how a full adder is built from half adders.

• $D = A \oplus B \oplus B_{in}$
• $B_{out} = (\overline{A} \cdot B) + (B_{in} \cdot \overline{(A \oplus B)})$

In practice, dedicated subtractor circuits are rarely built. Instead, most systems use an adder combined with two's complement to perform subtraction, which means the same hardware handles both operations.

Arithmetic and Overflow

Two's Complement Arithmetic

Two's complement is the standard way digital systems represent signed (positive and negative) integers. Positive numbers look the same as regular binary. To represent a negative number:

1. Start with the binary representation of the positive value.
2. Invert all the bits (flip 0s to 1s and 1s to 0s).
3. Add 1 to the result.

For example, in an 8-bit system, $+5$ is 00000101. To get $-5$: invert to get 11111010, then add 1 to get 11111011.

For $n$ bits, the representable range is $-2^{n-1}$ to $2^{n-1} - 1$. So an 8-bit system covers $-128$ to $+127$.

The big advantage of two's complement is that addition and subtraction use the same adder circuit. To subtract $B$ from $A$, you just negate $B$ (invert and add 1) and then add it to $A$. This is why most processors don't need separate subtractor hardware.

Overflow Detection

Overflow happens when the result of an arithmetic operation falls outside the representable range. In two's complement, this occurs when:

• Adding two positive numbers gives a negative result, or
• Adding two negative numbers gives a positive result.

Adding a positive number to a negative number can never overflow, because the result is always between the two operands.

The hardware detection method: compare the carry into the most significant bit (MSB) with the carry out of the MSB. If they differ, overflow has occurred. In Boolean terms, the overflow flag is:

$V = C_{in,MSB} \oplus C_{out,MSB}$

For example, in a 4-bit system, adding $0111$ (+7) and $0001$ (+1) gives $1000$ (-8), which is clearly wrong. The carry into bit 3 is 1 and the carry out of bit 3 is 0, so $V = 1$, flagging the overflow.

Detecting overflow matters because ignoring it leads to silently wrong results. Systems handle it in different ways: raising an exception, saturating to the max/min value, or setting a status flag for software to check.