Comparators
Greater, equal, or less
A comparator is a combinational circuit that reports whether one binary number is greater than, equal to, or less than another, built from per-bit equality (XNOR) and greater/less logic that resolves from the most significant bit downward.
The XNOR lesson built an equality comparator: one XNOR per bit asks 'do these two bits match?', and an AND over all of them asks 'do *all* the bits match?'. That answers
A = B, but a CPU usually needs more: not just *whether* two numbers are equal, but *which is larger*. This lesson extends the comparison to magnitude, producing three answers at once, A > B, A = B, and A < B, and connects it to the subtractor you already have.Comparing a single bit
Start with one bit each. For single bits
A and B the three relations have direct gate forms. A is greater only when A = 1 and B = 0; A is less only when A = 0 and B = 1; and they are equal when they match, which is exactly XNOR:GT = A · (¬B) LT = (¬A) · B EQ = ¬(A ⊕ B) = A XNOR B
| A | B | GT | EQ | LT |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 |
GT (A>B), EQ (A=B), LT (A<B) is 1 in every row. GT fires only on 1,0; LT only on 0,1; EQ on the two matching rows. These three outputs are mutually exclusive and always sum to one.GT = A AND NOT B, LT = NOT A AND B, and EQ = NOT (A XOR B). Open it in the lab and sweep A and B: exactly one of the three probes is high in each of the four cases.Comparing whole numbers: scan from the top
To compare multi-bit numbers, do what you do with two written numbers of the same length: scan from the most significant digit toward the least. The first place where the digits differ decides everything, and places that are equal are skipped.
1011 versus 1001: the top two bits match, then at the next bit A has 1 and B has 0, so A is greater and the remaining bits do not matter. This is the equal-so-far rule: keep comparing only while the higher bits have all been equal.It is the same reason
1011 beats 1009 in ordinary decimal: you read left to right, and the first column that differs settles it. A lower column can never overturn a decision already made by a higher one, because the higher column carries more weight. A magnitude comparator is that left-to-right scan frozen into gates.The bit-slice cell and cascading
That scan becomes one repeatable bit-slice cell that you stack from the most significant bit down. Each cell takes the running result from the bit above it (the cascade inputs
G_in, E_in, L_in, meaning 'greater so far', 'equal so far', 'less so far') and folds in its own bit pair to produce the running result for the bit below. With eq_i = a_i XNOR b_i for 'this bit matches':G_out = (a_i · ¬b_i) + (eq_i · G_in)
L_out = (¬a_i · b_i) + (eq_i · L_in) E_out = eq_i · E_in
Read
G_out aloud: A is greater so far if this bit makes it greater (a_i = 1, b_i = 0), or this bit is equal and A was already greater above. E_out insists every bit so far has matched. Seed the top (most significant) cell with G_in = 0, E_in = 1, L_in = 0 (nothing decided yet, equal so far), feed each cell's outputs into the next cell down, and the bottom cell's outputs are the final A > B, A = B, A < B. Because the cell is identical at every bit, you can cascade as many as you like, or chain whole comparator chips, by wiring one stage's outputs into the next stage's cascade inputs. This iterative structure is exactly how the classic 7485 comparator works.Comparing by subtracting
A CPU often skips the dedicated comparator entirely, because it already has a subtractor. Compute
A - B in the ALU and read the flags: the zero flag answers equality (A - B = 0 means A = B), and the sign of the difference answers order. This is why processors have a compare instruction that is really just a subtract that throws away the difference and keeps only the flags. No extra magnitude hardware needed, the ALU is already there.Common mistakes. Signed and unsigned comparison are not the same operation, even on identical bits. Take
A = 1111 1111 and B = 0000 0001. Read unsigned, A = 255 > 1, so A > B. Read as signed two's complement, A = -1 < +1, so A < B: the opposite answer. A plain magnitude comparator wired straight across the bits gives the unsigned result; for signed numbers you must compare differently. (A neat trick: flip just the two sign bits and then compare as unsigned, because inverting the top bit maps the signed order onto the unsigned order.) When comparing by subtraction, the sign flag alone is not enough for signed order either: signed A < B is the sign flag XOR the overflow flag, since the subtraction can overflow and flip the sign.Try it
Compare
A = 0110 and B = 0100 using the scan-from-the-top rule. Which bit decides it, and is A > B, A = B, or A < B? Then read the same bits as signed two's-complement values and confirm the answer is unchanged.Answer
Scan from the most significant bit. Bit 3:
0 = 0, equal, continue. Bit 2: 1 = 1, equal, continue. Bit 1: A has 1, B has 0, they differ, and A has the 1, so A > B and the lower bit is irrelevant. As unsigned, A = 6 > B = 4, agreeing. As signed, both top bits are 0, so both are positive (+6 and +4), and +6 > +4: the same answer. Signed and unsigned agree here precisely because neither number's sign bit is set; they disagree only when a sign bit comes into play.Compare-and-swap: making the answer act
A comparator *reports* an order; wire it to a multiplexer and it can *impose* one. A compare-and-swap takes two values
A and B and puts them in order on its two outputs: the larger leaves one side, the smaller the other. You already have every piece. Feed A and B into the magnitude comparator to read the GT flag (A > B), then let GT steer two muxes, one that always forwards the larger value and one that always forwards the smaller.- Compare: run
AandBthrough the magnitude comparator and keep just theGToutput (isAgreater thanB?). - Pick the larger: a mux selected by
GTpassesAwhenGT = 1, otherwiseB. That output is always the larger of the two (or either one, when they are equal). - Pick the smaller: a second mux on the same
GTline passesBwhenGT = 1, otherwiseA. That output is always the smaller. - The whole unit: two values in, the same two values out but sorted. Already in order they pass straight through; out of order they come out exchanged.
For multi-bit numbers each mux is really
n one-bit muxes sharing the single GT select line, so an n-bit compare-and-swap costs one comparator plus 2n bit-muxes: the comparator decides once, and the muxes route every bit of the two words the same way. That reuse is exactly why it pays to keep the comparator and the mux as ready-made blocks.Cascading swaps into a sorting network
One swap orders two values. To order more, arrange a fixed pattern of compare-and-swaps whose positions are decided in advance and never depend on the data. That fixed pattern is a sorting network: the numbers ride horizontal wires from left to right, and each compare-and-swap is a vertical rung joining two wires that it may exchange. Because the schedule of comparisons never changes, the whole sorter is pure combinational logic, with no clock, no loop, and no data-dependent branching.
Here is a network that sorts four values. Number the wires
w0 (top) through w3 (bottom); read left to right, and after the last rung w0 holds the smallest and w3 the largest. It uses five compare-and-swaps grouped into three stages:- Stage 1: swap
w0withw1, and at the same timew2withw3. The two rungs share no wire, so both act at once. - Stage 2: swap
w0withw2, andw1withw3. Again the two rungs share no wire and run together. After this stage the smallest of all four sits onw0and the largest onw3. - Stage 3: swap the two middle wires
w1andw2. Noww0 <= w1 <= w2 <= w3and the four numbers are fully sorted.
Parallel beats serial here. There are five swaps, yet the answer does not take five swap-delays. The two swaps inside a stage act on separate wires, so they settle at the same time; only the *stages* are sequential, since stage 2 needs stage 1's outputs and stage 3 needs stage 2's. If one compare-and-swap settles in time
t, the sorted result is ready after 3t (the number of stages, called the network's depth), not 5t. Running the swaps strictly one after another would cost 5t; doing the independent ones together shrinks the critical path down to the depth. It is the same propagation delay reasoning that sets a chip's clock-speed limit: what counts is the longest chain of *dependent* stages, not the total number of gates.Try it
In the four-input network above, suppose each compare-and-swap settles in 2 ns. How long until all four outputs are stable, and why is it not 10 ns even though there are five swaps?
Answer
6 ns. The five swaps fall into three stages (two swaps, then two, then one). The two swaps within a stage touch disjoint wires, so they settle at the same time and count as a single 2 ns delay for that stage. The stages are dependent, each needing the previous stage's outputs, so their delays add: three stages of 2 ns each is 6 ns. Ten nanoseconds would be the cost of running all five swaps strictly one after another; the network runs the independent swaps together, so its settling time is set by its depth (3 stages), not its swap count (5).
Comparison is how a program makes decisions: every
if, loop test, and branch rests on a comparator or a subtract-and-check-flags. The three outputs (greater, equal, less), together with the carry and overflow flags, are the status bits the control logic reads to choose what to do next. Next, the ALU bundles addition, subtraction, the bitwise operations, and these comparison flags into the one block at the heart of the CPU.Frequently asked
What is a digital comparator?
A digital comparator is a combinational circuit that compares two binary numbers and reports whether the first is greater than, equal to, or less than the second. Equality comes from a per-bit XNOR ANDed across all bits; magnitude comes from logic that scans the bits from most significant to least, with the first differing bit deciding the order.
How does a magnitude comparator compare multi-bit numbers?
It scans from the most significant bit downward and uses the 'equal so far' rule: as long as the higher bits all match, it keeps comparing, and the first bit where the two numbers differ settles which is larger. Each bit-slice cell takes 'greater/equal/less so far' from the bit above and folds in its own bit pair, so the cells cascade from the top bit down.
How does a 1-bit comparator work?
For single bits
A and B: A > B is A AND NOT B (true only for 1,0), A < B is NOT A AND B (true only for 0,1), and A = B is NOT (A XOR B), an XNOR (true when the bits match). Exactly one of the three outputs is 1 in each case.How does a CPU compare numbers without a separate comparator?
It subtracts. The ALU computes
A - B and reads the flags: the zero flag means A = B, and the sign of the difference gives the order. A processor's compare instruction is essentially a subtract that keeps only the flags and discards the difference, reusing the subtractor that is already there.Why do signed and unsigned comparisons differ?
Because the top bit means different things. Unsigned, all bits are positive weight, so a leading
1 makes a number large; signed two's-complement, the top bit has negative weight, so a leading 1 makes it negative. The bits 1111 1111 are 255 unsigned but -1 signed, so comparing them against 0000 0001 gives opposite answers. Hardware provides distinct signed and unsigned compare operations for exactly this reason.What is a compare-and-swap?
A compare-and-swap is a two-input building block that outputs its inputs in order: the larger on one wire and the smaller on the other. It is a magnitude comparator whose greater-than result drives two multiplexers, one selecting the larger value and one the smaller, so two numbers go in and a sorted pair comes out. Chaining many compare-and-swaps in a fixed pattern builds a sorting network.
What is a sorting network?
A sorting network is a fixed arrangement of compare-and-swap units that sorts a set of values with no clock, loop, or data-dependent branching, because the sequence of comparisons is fixed in advance. A four-value network needs five compare-and-swaps in three stages, and because swaps that touch different wires run in parallel, it settles in three swap-delays (its depth) rather than five.
Every lesson here builds toward one thing: a working CPU, from the transistor up.
Open the free lab →