# 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. Group: Arithmetic URL: https://digiwleea.wleeaf.dev/learn/comparator/ The [XNOR](https://digiwleea.wleeaf.dev/learn/xnor/) lesson built an **equality** comparator: one XNOR per bit asks 'do these two bits match?', and an [AND](https://digiwleea.wleeaf.dev/learn/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](https://digiwleea.wleeaf.dev/learn/subtract/) 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](https://digiwleea.wleeaf.dev/learn/xnor/): ``` GT = A · (NOT B) LT = (NOT A) · B EQ = NOT (A XOR 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 | _A 1-bit comparator. Exactly one of GT (A>B), EQ (A=B), LT (A **TIP:** 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 · NOT b_i) + (eq_i · G_in) ``` ``` L_out = (NOT 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](https://digiwleea.wleeaf.dev/learn/subtract/). Compute `A - B` in the [ALU](https://digiwleea.wleeaf.dev/learn/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](https://digiwleea.wleeaf.dev/learn/alu/) is already there. > **WARN:** **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](https://digiwleea.wleeaf.dev/learn/twos-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. **Q (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. **A:** 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](https://digiwleea.wleeaf.dev/learn/mux/) 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. 1. Compare: run `A` and `B` through the magnitude comparator and keep just the `GT` output (is `A` greater than `B`?). 2. Pick the larger: a [mux](https://digiwleea.wleeaf.dev/learn/mux/) selected by `GT` passes `A` when `GT = 1`, otherwise `B`. That output is always the larger of the two (or either one, when they are equal). 3. Pick the smaller: a second mux on the same `GT` line passes `B` when `GT = 1`, otherwise `A`. That output is always the smaller. 4. 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. > **TIP:** 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](https://digiwleea.wleeaf.dev/learn/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: 1. Stage 1: swap `w0` with `w1`, and at the same time `w2` with `w3`. The two rungs share no wire, so both act at once. 2. Stage 2: swap `w0` with `w2`, and `w1` with `w3`. Again the two rungs share no wire and run together. After this stage the smallest of all four sits on `w0` and the largest on `w3`. 3. Stage 3: swap the two middle wires `w1` and `w2`. Now `w0 <= w1 <= w2 <= w3` and the four numbers are fully sorted. > **TIP:** **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](https://digiwleea.wleeaf.dev/learn/timing/) reasoning that sets a chip's clock-speed limit: what counts is the longest chain of *dependent* stages, not the total number of gates. **Q (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? **A:** 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). > **KEY:** 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](https://digiwleea.wleeaf.dev/learn/overflow/) flags, are the status bits the control logic reads to choose what to do next. Next, the [ALU](https://digiwleea.wleeaf.dev/learn/alu/) bundles addition, subtraction, the bitwise operations, and these comparison flags into the one block at the heart of the CPU. ### FAQ **Q:** What is a digital comparator? **A:** 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](https://digiwleea.wleeaf.dev/learn/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. **Q:** How does a magnitude comparator compare multi-bit numbers? **A:** 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. **Q:** How does a 1-bit comparator work? **A:** 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](https://digiwleea.wleeaf.dev/learn/xnor/) (true when the bits match). Exactly one of the three outputs is `1` in each case. **Q:** How does a CPU compare numbers without a separate comparator? **A:** It subtracts. The [ALU](https://digiwleea.wleeaf.dev/learn/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](https://digiwleea.wleeaf.dev/learn/subtract/) that is already there. **Q:** Why do signed and unsigned comparisons differ? **A:** 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. **Q:** What is a compare-and-swap? **A:** 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](https://digiwleea.wleeaf.dev/learn/mux/), 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. **Q:** What is a sorting network? **A:** 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.