The Hardware Implementation of Arithmetic

The second lesson stated that the add instruction writes a result to register 66, but left open how that result is produced. This lesson fills that gap: what structures in hardware carry out addition?

The answer combines two lessons from the first topic: the AND, OR, and XOR operations defined in the bit-level operations lesson, and the two’s complement representation defined in the signed integers lesson. Brought together, these two build the entire arithmetic unit.

Logic Gates

A logic gate is a physical circuit element that produces one output bit from one or two input bits. Its behavior is identical to the truth tables defined in the previous topic: an AND gate produces $1$ only if both inputs are $1$, an OR gate if at least one is $1$, an XOR gate if the inputs differ.

This also explains the origin of that lesson’s operators: the expression a & b means as many AND gates as the word is wide, all operating at once. This is why bit-level operations are cheap — a single gate suffices per bit, and bits do not wait on each other.

Arithmetic, however, breaks this independence: a digit’s result depends on the carry bit coming from the digits below it.

The Half Adder

Adding two bits is the same as addition done by hand. The operation $1 + 1$ leaves $0$ at that digit and carries $1$ to the digit above.

$a$	$b$	Sum	Carry
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

The sum column is identical to the XOR table, the carry column to the AND table:

$$\text{sum} = a \oplus b, \qquad \text{carry} = a \wedge b$$

This two-gate circuit is called a half adder. Its name reflects a deficiency: it does not account for the carry coming from the digit below.

The Full Adder

In a real addition, every digit has three inputs: two bits and the carry coming from the digit below. The circuit that processes these three inputs is the full adder:

$$\text{sum} = a \oplus b \oplus c_{\text{in}}$$

$$c_{\text{out}} = (a \wedge b) \vee \big(c_{\text{in}} \wedge (a \oplus b)\big)$$

The carry expression can be read in words: a carry is produced if both bits are $1$; or if exactly one bit is $1$ and a carry comes from the digit below.

The Ripple-Carry Adder

An $n$-bit addition is built by chaining $n$ full adders: each adder’s carry output connects to the carry input of the adder above it. This arrangement is called a ripple-carry adder.

The chain has a cost: the top digit’s result is not stable until the carry bit has propagated through every digit. The circuit’s delay grows in proportion to the number of bits.

Reducing this delay is a classic problem in digital design. Designs that compute carry bits directly from the input bits, rather than waiting for them digit by digit — carry-lookahead adders — achieve shorter delay by using more gates. This trade-off between area and speed repeats at every layer of hardware design.

Subtraction Needs No Separate Circuit

The signed integers lesson stated that two’s complement is preferred because it leaves the addition circuit unchanged. Its counterpart in the circuit is this:

$$a - b = a + (\lnot b) + 1$$

The value $\lnot b$ is produced by passing $b$’s bits through XOR gates; the trailing $+1$ is supplied by feeding $1$ into the lowest adder’s carry input. A single control bit thus governs both the inversion and the carry input: at $0$ the circuit performs addition, at $1$ it performs subtraction.

Comparison operations use the same circuit. Comparing two values means computing their difference and examining the result’s flags; the result itself is not stored.

Status Flags

The arithmetic and logic unit produces, alongside the result, bits that qualify it. Four flags are common:

Flag	Condition that sets it
Zero	All bits of the result are $0$
Sign	The result’s leftmost bit is $1$
Carry	The carry out of the top digit is $1$ (unsigned overflow)
Overflow	The carry into and out of the top digit differ (signed overflow)

The last row is the hardware definition of signed overflow. When two positive numbers are added, if a carry enters the top digit but does not exit it, the result has overflowed into the sign bit — the value appears negative. This is exactly what happens in the example $127 + 1$.

Keeping the carry and overflow flags separate lets the same addition circuit support both the unsigned and signed interpretations. Which flag is meaningful is decided by the program, which knows under which interpretation it is using the value. Conditional branch instructions also read these flags.

Building the Circuit in a Program

The following program builds the full adder and an eight-bit ripple-carry adder using bit-level operators:

def full_adder(a: int, b: int, carry_in: int) -> tuple[int, int]:
    """Produces the sum and carry-out bits from three input bits."""
    total = a ^ b ^ carry_in
    carry_out = (a & b) | (carry_in & (a ^ b))
    return total, carry_out


def add(x: int, y: int, bits: int = 8, subtract: bool = False) -> dict:
    """Ripple-carry adder; if subtract=True, computes x - y."""
    carry = 1 if subtract else 0
    result = 0
    for i in range(bits):
        a = (x >> i) & 1
        b = ((y >> i) & 1) ^ (1 if subtract else 0)   # b is inverted for subtraction
        if i == bits - 1:
            top_carry_in = carry                      # carry entering the top digit
        t, carry = full_adder(a, b, carry)
        result |= t << i
    return {
        "result": result,
        "zero": result == 0,
        "sign": ((result >> (bits - 1)) & 1) == 1,
        "carry": carry == 1,
        "overflow": top_carry_in != carry,
    }


print(add(5, 3))                     # 8, no overflow
print(add(5, 3, subtract=True))      # 2, subtraction in the same circuit
print(add(127, 1)["overflow"])       # True  — signed overflow
print(add(255, 1)["carry"])          # True  — unsigned overflow
print(add(255, 1)["result"])         # 0     — wrapped around

The subtract flag being used in two places at once — both in inverting b’s bits and in the initial carry — is the counterpart of the single control bit in hardware.

The outputs confirm the claims made in the first topic: $255 + 1$ wraps around under the unsigned interpretation, $127 + 1$ sets the overflow flag under the signed interpretation. That lesson stated that “hardware reports both kinds of overflow through separate flags”; the circuit in this lesson is the very structure that produces those flags.

Summary

• Logic gates are the physical counterpart of bit-level operators; because every bit is processed independently, these operations are cheap.
• A half adder adds two bits: the sum is produced by an XOR gate, the carry by an AND gate.
• A full adder also accounts for the carry from the digit below; chaining $n$ full adders gives an $n$-bit adder.
• Chaining delay grows with the number of bits; carry-lookahead designs reduce the delay by using more gates.
• Subtraction needs no separate circuit: the second operand is inverted and $1$ is fed into the carry input.
• Alongside the result, the arithmetic unit produces zero, sign, carry, and overflow flags; carry reports overflow under the unsigned interpretation, overflow under the signed one.

Next Step

This topic has established how data resides in memory and how instructions are executed in hardware. One link remains: how does the text a programmer writes turn into these instructions? The next topic covers the chain that reaches from source code to a running process — the steps of compiling, linking, and loading.