Adders and Flip-Flops
You can now wire
logic circuits
out of AND, OR and NOT gates. But a pile of gates is only interesting once it does a job.
This page builds the two jobs that a whole computer is made from: arithmetic and
memory. We meet the adder — a circuit that adds binary digits,
the beating heart of the CPU's arithmetic unit — and the flip-flop — a circuit
that remembers a single bit, the raw material of every register and every byte of RAM.
These two circuits also mark a great divide in digital electronics. An adder is
combinational: its output depends only on the inputs in front of it right now, with
no history. A flip-flop is sequential: its output depends on the inputs
and on what it is already storing. That one difference — whether a circuit has a memory —
is the line between a pocket calculator and a computer.
Binary addition, one column at a time
Adding binary numbers works exactly like adding decimal numbers: line the digits up in columns and
add each column, carrying into the next when a column overflows. In binary a single column can only
hold a 0 or a 1, so as soon as two bits add up
to 2 we must carry:
0+0 = 0 \qquad 0+1 = 1 \qquad 1+0 = 1 \qquad 1+1 = 10
That last case is the whole story. 1+1 is 2,
which in binary is 10 — a sum bit of
0 and a carry bit of 1. So
adding two bits never produces one answer; it produces two outputs: a sum and a carry.
A circuit that computes both from two input bits is called a half adder.
The half adder
Look hard at the four cases of A+B and two familiar patterns jump out.
The sum bit is 1 exactly when the two inputs
differ — that is the XOR ("exclusive OR") gate. The carry
bit is 1 only when both inputs are 1 —
that is plain AND. Here is the truth table with both outputs:
So the entire half adder is just two gates sharing the same two inputs:
\text{Sum} = A \oplus B \qquad\qquad \text{Carry} = A \cdot B
Press play to watch it wired up: the two inputs fan out to an XOR gate (giving the
sum) and an AND gate (giving the carry).
It is called a half adder because it is only half the job. It can add the two bits in a
single column, but it has nowhere to accept a carry coming in from the column to its right.
To add real multi-bit numbers we need a version with three inputs.
XOR — exclusive OR, written \oplus — outputs
1 when its inputs are different and 0
when they are the same. Compare it with plain OR: OR says "at least one is on", so
1 \text{ OR } 1 = 1; XOR says "exactly one is on", so
1 \oplus 1 = 0. That is precisely what column addition wants: when both
bits are 1 the sum digit is 0 and the
1 is carried away. XOR is the "add without the carry" gate, which is why
it turns up at the heart of every adder (and, later, in checksums, parity bits and cryptography).
The full adder
A full adder fixes the half adder's blind spot by taking three inputs: the
two bits for this column, A and B, plus a
carry-in C_{\text{in}} from the column on its right. It
still produces a sum and a carry, but now the sum can be as large as
1+1+1 = 3 = 11_2. Three inputs means
2^3 = 8 rows:
Read the outputs as a single two-bit number
C_{\text{out}}\,\text{Sum} and each row just counts how many of the three
inputs are on: no ones on gives 00, one on gives
01, two on give 10, three on give
11. In Boolean terms the sum is a three-way XOR and the carry is "any two
of the three inputs are on":
\text{Sum} = A \oplus B \oplus C_{\text{in}}
\qquad
C_{\text{out}} = (A \cdot B) + (C_{\text{in}} \cdot (A \oplus B))
Neatly, a full adder can be built from two half adders and an OR gate: the first
half adder adds A and B; the second adds the
carry-in to that partial sum; and an OR gate joins the two possible carries. Step through the wiring:
Chaining full adders: the ripple-carry adder
One full adder handles a single column. To add two whole binary numbers you line up
one full adder per bit and wire each adder's carry-out into the next adder's
carry-in — exactly like carrying the 1 when you add by hand. The carry
"ripples" leftward from the least-significant bit to the most, which is why this is called a
ripple-carry adder.
The rightmost stage has no carry to receive, so its carry-in is fixed at
0 (a half adder would do there). Add more stages and you can add wider
numbers: eight full adders add two 8-bit bytes; sixty-four of them add the 64-bit integers in a
modern CPU. This chain of adders is the "A" in the ALU (Arithmetic Logic Unit).
A full adder is just a rule, so we can write one function and call it in a loop, feeding each
stage's carry-out into the next stage's carry-in. Press Run to add two 4-bit
numbers bit by bit and watch the carry ripple.
// One full adder: returns this column's sum bit and carry-out.
function fullAdder(a: number, b: number, cin: number): { sum: number; cout: number } {
const sum: number = a ^ b ^ cin; // three-way XOR
const cout: number = (a & b) | (cin & (a ^ b)); // "any two of three"
return { sum, cout };
}
// Ripple-carry add two 4-bit numbers, least-significant bit first.
const A: number[] = [1, 0, 1, 1]; // bits, LSB first → 1101b = 13
const B: number[] = [1, 1, 1, 0]; // bits, LSB first → 0111b = 7
const out: number[] = [];
let carry: number = 0;
for (let i = 0; i < 4; i++) {
const r = fullAdder(A[i], B[i], carry);
out[i] = r.sum;
carry = r.cout; // ripple into the next column
}
out[4] = carry; // final carry becomes the top bit
console.log("sum bits (LSB first):", out.join(""));
console.log("decimal:", out.reduce((acc, bit, i) => acc + bit * 2 ** i, 0));
It prints 13 + 7 = 20. Every desktop, phone and games console adds
numbers with hardware doing precisely this — gates switching, a carry rippling along.
A circuit that remembers: the flip-flop
Every circuit so far has been combinational: the output is a pure function of the
inputs on the wires right now. Cut the power and there is nothing to lose — feed the same inputs back
and you get the same output. That can never store anything. To build memory we need a circuit whose
output can persist after the input that set it has gone. The trick is
feedback: wire a gate's output back to its own input, so the circuit holds itself in
a state.
The simplest such circuit is the SR flip-flop (also called an SR latch), built from
two cross-coupled NOR gates. It has two inputs — S (set) and R
(reset) — and one stored output Q:
- Set (S=1, R=0): forces Q=1.
- Reset (S=0, R=1): forces Q=0.
- Hold (S=0, R=0): Q keeps
whatever value it had — this is the memory.
- Forbidden (S=1, R=1): drives both outputs the same
way and leaves the latch in an undefined state — a design must avoid it.
Notice the hold row: with both inputs 0 the output is
not determined by the inputs at all — it depends on the flip-flop's stored state. That is
the definition of sequential logic. Here is the characteristic truth table, with
Q_{\text{prev}} standing for the currently stored bit:
The D flip-flop: one bit of storage
The raw SR latch has that awkward forbidden input and it changes the instant its inputs change. Real
computers tidy both problems up with the D flip-flop ("D" for data or
delay). It has a single data input D and a clock input.
On the tick of the clock it copies whatever is on D into
Q; between ticks it holds that value no matter how D
wobbles. In short: store this bit now, and remember it until the next tick.
A D flip-flop stores exactly one bit. Line up eight of them, all sharing one clock, and you have an
8-bit register — the CPU's short-term scratchpad. Line up millions and you have the
fast memory (cache and registers) a processor works from. Every value a computer "holds onto", from
the number in a loop counter to the pixels queued for the screen, is ultimately sitting in
flip-flops built from feedback loops of gates.
The clock deserves a moment. A computer's clock is a signal that pulses billions of
times a second (a 3\,\text{GHz} CPU ticks
3 \times 10^{9} times per second). Each tick tells every flip-flop
"capture your input now", so the whole machine updates its stored state in lock-step. Without
a clock, sequential circuits would race ahead of one another and the stored data would scramble.
The single most important idea on this page is the distinction between the two kinds of circuit —
and it is easy to blur:
-
Combinational logic has no memory. An adder (half or full) is combinational: its
output depends only on the inputs present right now. The same inputs always give the
same output, every time, regardless of what happened before. There is no notion of "state".
-
Sequential logic remembers. A flip-flop is sequential: its output depends on the
inputs and on the bit it is currently storing. So the same inputs can give different
outputs — in the SR latch, S=0, R=0 leaves
Q at whatever it already was. This dependence on stored state is
exactly what makes memory possible.
Test yourself with the classic trap: "does an adder store the last number it added?" No — it is
combinational, it holds nothing. To remember a result you must latch it into flip-flops. Feedback
(an output wired back to an input) is the tell-tale sign of a sequential circuit; a purely
left-to-right circuit with no loop back is combinational.
The name is delightfully literal. The circuit has two stable states —
Q=0 and Q=1 — and a pulse on the right input
makes it flip from one to the other, then a pulse on the other input makes it
flop back. Because it rests in either state indefinitely (thanks to the feedback holding
it there), it is also called a bistable: "two stable states". Two cross-coupled
gates, forever leaning on each other, is all it takes to remember a single yes-or-no.
The big picture
Put the two halves of this page together and you have, in miniature, a whole computer. The
adder (combinational) does the arithmetic; the flip-flop
(sequential) holds the numbers and results between one clock tick and the next. Add on multiplexers to
route data and you can build the datapath of a real CPU. Everything a computer does reduces to
combinational circuits computing new values and sequential circuits remembering
them — a rhythm of "work it out, store it, work out the next thing", keeping time to the clock.