Skip to content
Tutorials Center
My learning

Topics

Lesson 25 of 57 · Combinational Building Blocks

Subtractors and Comparators

Design half and full subtractors, turn an adder into an adder-subtractor with two's complement, and build 1-bit and n-bit magnitude comparators in runnable Python.

An adder tells a computer how to combine numbers. Two more questions come up all the time: "what is the difference between these numbers?" and "which one is bigger?" The first is answered by a subtractor, the second by a comparator. Every if (a < b) in a program ends up as a comparator circuit in hardware, and every a - b as a subtractor.

You will build subtractors the long way (mirroring the half and full adder), then discover why almost no real processor does that: it reuses the adder with two's complement. After that you will build comparators bit by bit and as an n-bit circuit.

The half subtractor

Subtracting a single bit works like decimal subtraction with borrowing. In A - B, the only awkward case is 0 - 1: the answer is 1 and you borrow from the next column. A half subtractor has two outputs, the difference D and the borrow Bout.

A B D Bout
0 0 0 0
0 1 1 1
1 0 1 0
1 1 0 0

The difference column is the same as for the half adder, so D = A ⊕ B. The borrow is 1 only when A = 0 and B = 1, so Bout = A′·B. Compared to the half adder, only one input of the AND gate is inverted.

The full subtractor

Just as a full adder accepts a carry from the column on the right, a full subtractor accepts a borrow Bin from it. It computes A - B - Bin:

D = A ⊕ B ⊕ Bin

Bout = A′·B + (A ⊕ B)′·Bin

The difference works out the same as the sum of a full adder. A borrow comes out when A is 0 and B is 1 (A′·B), or when A and B are equal and an incoming borrow still has to be paid, which is (A ⊕ B)′·Bin. In the program below, a full subtractor is built from two half subtractors and an OR gate, and the last column checks every row: A - B - Bin must equal D - 2·Bout (a borrow costs two in this column).

Python Half and full subtractor truth tables

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Subtraction with an adder

A processor does not need a separate subtractor, because subtraction is addition in disguise. As you saw in signed numbers and two's complement, A - B = A + (−B), and the two's complement of B is "invert every bit, then add 1". Both steps are cheap:

  1. Put an XOR gate on each B input. With a control line SUB on the other XOR input, B ⊕ SUB passes B through unchanged when SUB = 0 and inverts it when SUB = 1.
  2. Feed SUB into the adder's carry-in. The "+1" of the two's complement is free: it is the carry-in that the adder already had.

One ripple-carry adder plus n XOR gates is now an adder-subtractor: SUB = 0 gives A + B, SUB = 1 gives A - B. The overflow flag works exactly as before, and the final carry-out has a useful meaning for unsigned numbers: it is the opposite of a borrow. A carry-out of 1 means A >= B (no borrow needed); a carry-out of 0 means the subtraction had to borrow, so A < B.

One adder, two jobs

XOR on B Flips every bit when SUB is 1.
Carry in SUB also supplies the +1.
Result A + (NOT B) + 1 equals A minus B.

Subtraction costs only n XOR gates extra.

1 / 2

The next program is a 4-bit adder-subtractor that goes through each bit with the full-adder equations. It prints a few subtractions in binary together with the carry and overflow flags, then tests the unit against Python's arithmetic for all 256 input pairs, both for addition and for subtraction.

Python A 4-bit adder-subtractor

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the carry column. 9 - 3 and 5 - 5 and 2 - 1 give carry 1 (no borrow), while 3 - 9 gives carry 0, because the true answer is negative and the unsigned pattern 1010 is the wrapped value 10. The signed columns show the other reading: 7 - 12 as signed numbers is 7 - (-4) = 11, which does not fit in four bits, and the overflow flag is 1.

Comparing two numbers

A magnitude comparator has three outputs: A > B, A = B and A < B. Exactly one of them is 1.

For a single bit the equations come straight from the truth table:

  • A > B is A·B′ (A is 1, B is 0)
  • A = B is (A ⊕ B)′ (an XNOR gate; the bits agree)
  • A < B is A′·B

You can reuse parts: the greater-than output of a 1-bit comparator is the same as the borrow of a subtractor with A and B swapped, which is why subtraction can serve as a comparison.

For n bits, compare like a dictionary compares words. Start from the most significant bit. The first position where the bits differ decides the whole comparison. If every position matches, the numbers are equal. In gate terms, for 4 bits (with Ei meaning bit i is equal, an XNOR):

A = B is E3·E2·E1·E0

A > B is A3·B3′ + E3·A2·B2′ + E3·E2·A1·B1′ + E3·E2·E1·A0·B0′

The loop in the code does the same thing: eq stays 1 while all higher bits match, and a bit pair can only set gt or lt while eq is still 1.

Python 1-bit and 4-bit comparators

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The pair 0111 versus 1000 shows the most-significant-first rule: bit 3 already differs, so 7 < 8 is decided immediately, even though the lower three bits of 0111 are all ones.

Building wide comparators

Comparator chips often have cascade inputs (A>B in, A=B in, A<B in). The result of a lower-order comparator feeds these inputs of a higher-order one, and they only matter when the current four bits are equal. Chain two 4-bit comparators and you have an 8-bit one, the same way adders are chained. Note the direction: the higher digits get the decision, and the lower digits act as the tie-breaker.

Comparing signed numbers needs one extra step. The pattern 1000 is bigger than 0111 as unsigned numbers but smaller as signed ones (-8 against 7). A signed comparator treats the sign bit specially: a negative number is always smaller than a non-negative one, and for equal signs the unsigned comparison works.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. What are the equations of a half subtractor for A - B?

    The difference is 1 when the inputs differ (XOR). A borrow is needed only for 0 - 1, which is A′·B.
  2. 2. In an adder-subtractor, what happens when SUB = 1?

    Inverting B and adding 1 gives the two's complement of B, so A + (−B) is A - B. SUB drives both the XOR gates and the carry-in.
  3. 3. After an unsigned subtraction A - B on an adder-subtractor, the final carry-out is 0. What does that mean?

    With subtraction done as addition, carry-out is the opposite of borrow. A carry-out of 0 means a borrow happened, so A < B.
  4. 4. When comparing two 4-bit numbers, which bit do you look at first?

    The most significant bit carries the most weight. The first position, scanning from the top, where the bits differ decides which number is larger.
  5. 5. Which gate gives the A = B output of a 1-bit comparator?

    XNOR is 1 exactly when its two inputs are equal, so it is the 1-bit equality test.

Summary

  • A half subtractor is D = A ⊕ B, Bout = A′·B; a full subtractor adds a borrow input: D = A ⊕ B ⊕ Bin.
  • Hardware subtracts by adding the two's complement: XOR gates invert B and the carry-in supplies the +1, so one adder serves both operations.
  • For unsigned subtraction, carry-out 1 means no borrow (A >= B) and carry-out 0 means a borrow.
  • A 1-bit comparator uses A·B′, XNOR and A′·B for greater, equal and less.
  • An n-bit comparator scans from the most significant bit; the first differing bit decides, and equality needs all XNORs to be 1.
  • Wider comparators are built by cascading smaller ones, with the lower digits acting as tie-breakers.

Next: Multiplexers and Demultiplexers.