---
title: 'The Hardware Implementation of Arithmetic'
source: 'https://academia.sh/en/courses/how-computers-work/hardware-implementation-of-arithmetic'
course: 'How Computers Work'
language: en
updated: '2026-08-17T18:08:12+00:00'
license: 'CC BY-SA 4.0'
---

# The Hardware Implementation of Arithmetic

From logic gates to adder circuits, how subtraction reuses the same circuit, and how status flags are produced.

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:

```python
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.