Chapter 13 of 32

Subtractors

In Half & Full Adders we built circuits that add bits. Subtraction needs its own circuits too, or does it? In this chapter we design the half subtractor and the full subtractor exactly as we designed the adders, chain them into an n-bit subtractor, and then see why real processors almost never use them: an adder plus a few XOR gates can subtract just as well, using 2's complement.

First, recall how you subtract binary numbers by hand. When the top bit is smaller than the bottom bit, you borrow 1 from the next column, which is worth 2 in the current column:

  borrow out: 0 1 1 1     (1 = this column borrows from the column on its left)
              1 0 1 0     (10)
            − 0 1 1 1     (7)
            ---------
              0 0 1 1     (3)

Column 0:  0 − 1        → borrow 1, so (2 + 0) − 1 = 1
Column 1:  1 − 1 − 1    → borrow 1, so (2 + 1) − 1 − 1 = 1
Column 2:  0 − 1 − 1    → borrow 1, so (2 + 0) − 1 − 1 = 0
Column 3:  1 − 0 − 1    → no borrow,       1 − 0 − 1 = 0

Just like addition, the rightmost column handles 2 bits (A − B) and every other column handles 3 bits (A − B − borrow-in). Each column produces a difference bit D and a borrow-out bit.


Half Subtractor

A half subtractor subtracts one bit B from another bit A and produces a difference D and a borrow Bout, where A − B = D − 2·Bout.

The borrow has weight −2 because borrowing means "I took 2 from the next column".

A

B

Bout

D

Meaning

0

0

0

0

0 − 0 = 0

0

1

1

1

0 − 1: borrow, (2 + 0) − 1 = 1

1

0

0

1

1 − 0 = 1

1

1

0

0

1 − 1 = 0

D    = A′B + AB′ = A ⊕ B
Bout = A′B

Compare with the half adder (S = A ⊕ B, C = AB): the difference is identical to the sum. Only the borrow differs, and the only change is that A is complemented. That makes sense: a borrow is needed only when A = 0 and B = 1.

A ──┬───────────────────┐
    │                 [XOR]────── D = A ⊕ B
B ──┼──┬────────────────┘
    │  │
    └──┼──[NOT]── A′ ───┐
       │              [AND]────── Bout = A′B
       └────────────────┘

Half Subtractor with NAND Gates Only

n1   = (A·B)′
n2   = (A·n1)′          = (AB′)′
n3   = (B·n1)′          = (A′B)′
D    = (n2·n3)′         = AB′ + A′B = A ⊕ B
Bout = (n3·n3)′         = A′B

Total: 5 NAND gates

Notice the nice reuse: the internal signal n3 of the NAND XOR already equals (A′B)′, so one more NAND used as an inverter gives the borrow. (In the half adder we inverted n1 instead.)


Full Subtractor

A full subtractor computes A − B − Bin, where Bin is the borrow taken by the column on the right. It outputs a difference D and a borrow Bout such that A − B − Bin = D − 2·Bout.

Row

A

B

Bin

A − B − Bin

Bout

D

0

0

0

0

0

0

0

1

0

0

1

−1

1

1

2

0

1

0

−1

1

1

3

0

1

1

−2

1

0

4

1

0

0

1

0

1

5

1

0

1

0

0

0

6

1

1

0

0

0

0

7

1

1

1

−1

1

1

Check one row with the definition: row 3, 0 − 1 − 1 = −2 = 0 − 2·1, so D = 0 and Bout = 1. Row 7, 1 − 1 − 1 = −1 = 1 − 2·1, so D = 1 and Bout = 1.

Difference

D = Σm(1, 2, 4, 7) = A ⊕ B ⊕ Bin

Exactly the same minterms as the full adder's sum: the K-map is the same checkerboard. Whether you add or subtract, the result bit is 1 when an odd number of the three inputs are 1.

Borrow

Bout = Σm(1, 2, 3, 7)

          B Bin
  A     00   01   11   10
  0  |  0  |  1  |  1  |  1  |
  1  |  0  |  0  |  1  |  0  |

  pair (1,3) → A′·Bin      pair (2,3) → A′B      pair (3,7) → B·Bin

Bout = A′B + A′·Bin + B·Bin

This is the full adder's carry with A replaced by A′. Intuition: a borrow is needed when the "amount to take away" (B + Bin) is larger than A. If A = 0, any 1 in B or Bin causes a borrow; if A = 1, you need both B and Bin to be 1.

The second, half-subtractor-friendly form is:

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

Check: (A ⊕ B)′ = A′B′ + AB, so Bin(A ⊕ B)′ = A′B′Bin + ABBin
       A′B + A′B′Bin + ABBin  →  minterms 2,3 + 1 + 7 = Σm(1, 2, 3, 7)  ✓

Full Subtractor from Two Half Subtractors

             +---------+  D1 = A⊕B   +---------+
  A ───────> |         |───────────> |         |─────────────────> D = A⊕B⊕Bin
             |   HS1   |             |   HS2   |
  B ───────> |         |   Bin ────> |         |
             +---------+             +---------+
                  │ B1 = A′B              │ B2 = (A⊕B)′·Bin
                  │                       │
                  └─────────>[ OR ]<──────┘
                               │
                               └─────────────────────────────────> Bout

HS1 computes A − B; HS2 subtracts Bin from that difference (D1 goes to HS2's "A" input and Bin to its "B" input). The borrows can never both be 1: B1 = 1 requires A ≠ B, which makes D1 = 1 and so B2 = D1′·Bin = 0. Hence (as for the adder) the OR could be an XOR.

Full Subtractor with 9 NAND Gates

n1 = (A·B)′        n2 = (A·n1)′       n3 = (B·n1)′ = (A′B)′
x  = (n2·n3)′      = A ⊕ B
n5 = (x·Bin)′      n6 = (x·n5)′       n7 = (Bin·n5)′ = ((A⊕B)′·Bin)′
D    = (n6·n7)′    = A ⊕ B ⊕ Bin
Bout = (n3·n7)′    = A′B + (A⊕B)′·Bin

9 NAND gates, the same count as the full adder. All of these netlists were checked by enumerating every input combination.


Adder vs Subtractor Side by Side

Circuit

Result bit

Carry / borrow

Half adder

S = A ⊕ B

C = AB

Half subtractor

D = A ⊕ B

Bout = A′B

Full adder

S = A ⊕ B ⊕ Cin

Cout = AB + ACin + BCin

Full subtractor

D = A ⊕ B ⊕ Bin

Bout = A′B + A′Bin + BBin

The pattern "complement A in the carry equation" lets you turn an adder into a subtractor with one inverter: feed A′ to the carry logic only. A popular exam question asks exactly this.


n-bit Ripple-Borrow Subtractor

Chain n full subtractors, connecting each Bout to the next stage's Bin, with Bin = 0 at the least significant stage:

   A3 B3        A2 B2        A1 B1        A0 B0
    |  |         |  |         |  |         |  |
  +------+  b3 +------+  b2 +------+  b1 +------+
b4| FS3  |<----| FS2  |<----| FS1  |<----| FS0  |<-- 0
  +------+     +------+     +------+     +------+
     |            |            |            |
     D3           D2           D1           D0

For unsigned numbers, the final borrow b4 tells you the sign of the true result: b4 = 1 means A < B, and D then holds A − B + 24.

Worked Example: 1010 − 0111

Stage

Ai

Bi

Bin

Ai − Bi − Bin

Di

Bout

0

0

1

0

−1

1

1

1

1

1

1

−1

1

1

2

0

1

1

−2

0

1

3

1

0

1

0

0

0

D = 0011 = 3 and final borrow 0, so 10 − 7 = 3 with no underflow. This matches the hand calculation at the top of the chapter. Like the ripple-carry adder, the borrow must ripple through every stage, so the delay grows linearly with n.


Subtraction Using an Adder (2's Complement)

Building a separate subtractor next to the adder wastes hardware. Instead, use the identity from Number Systems & Binary Codes:

A − B = A + (2's complement of B) = A + B′ + 1 (in n bits, ignoring the carry out of the top bit).

So: invert every bit of B and set the adder's input carry C0 to 1. The "+1" costs nothing: it uses the otherwise idle carry input of the least significant full adder.

Same Example: 1010 − 0111

B  = 0111   →   B′ = 1000

     1 0 1 0        (A)
   + 1 0 0 0        (B′)
   +       1        (C0 = 1)
   ---------
   1 0 0 1 1        carry out C4 = 1, result 0011 = 3  ✓

Notice C4 = 1 here, while the ripple-borrow subtractor gave borrow 0. For unsigned numbers the two are always complements of each other:

Using A + B′ + 1 for unsigned subtraction: Cout = 1 means no borrow (A ≥ B); Cout = 0 means a borrow occurred (A < B).

(Processors differ in how they report this: x86 sets its carry flag to the borrow, while ARM sets its carry flag to the adder's raw carry-out, i.e. NOT borrow.)

The Adder-Subtractor Circuit

One control bit M chooses the operation. Each Bi passes through an XOR gate with M, because Bi ⊕ 0 = Bi and Bi ⊕ 1 = Bi′; and M also drives C0:

            B3        B2        B1        B0
             |         |         |         |
  M ──+───[XOR]─────[XOR]─────[XOR]─────[XOR]
      |      |         |         |         |
      |   A3 |      A2 |      A1 |      A0 |
      |    | |       | |       | |       | |
      |  +----+ C3 +----+ C2 +----+ C1 +----+
 C4 <────| FA |<---| FA |<---| FA |<---| FA |<──── C0 = M
      |  +----+    +----+    +----+    +----+
      |    |         |         |         |
      |    S3        S2        S1        S0

  M = 0:  S = A + B          M = 1:  S = A + B′ + 1 = A − B
  Signed overflow:  V = C4 ⊕ C3

The overflow rule (carry into the sign bit differs from the carry out of it) is valid for both addition and subtraction of 2's complement numbers.

Simulating the Adder-Subtractor

The SystemVerilog below builds the 4-bit adder-subtractor from full adders, prints a few interesting cases, and then checks all 512 combinations of A, B and M:

module full_adder (input  logic a, b, cin,
                   output logic s, cout);
  assign s    = a ^ b ^ cin;
  assign cout = (a & b) | (cin & (a ^ b));
endmodule

// m = 0: s = a + b      m = 1: s = a - b
module add_sub4 (input  logic [3:0] a, b,
                 input  logic       m,
                 output logic [3:0] s,
                 output logic       c4, v);
  logic [4:0] c;
  logic [3:0] bx;
  assign c[0] = m;
  assign bx   = b ^ {4{m}};          // invert b when subtracting
  genvar i;
  for (i = 0; i < 4; i++) begin : stage
    full_adder fa (.a(a[i]), .b(bx[i]), .cin(c[i]), .s(s[i]), .cout(c[i+1]));
  end
  assign c4 = c[4];
  assign v  = c[4] ^ c[3];          // signed overflow
endmodule

module tb;
  logic [3:0] a, b, s;
  logic m, c4, v;
  int errors = 0;
  add_sub4 dut (.*);
  task show(input [3:0] x, y, input mode);
    a = x; b = y; m = mode; #1;
    $display("%b %s %b = %b  C4=%b V=%b   unsigned %2d %s %2d -> %2d   signed %2d %s %2d -> %2d",
             a, m ? "-" : "+", b, s, c4, v,
             a, m ? "-" : "+", b, s,
             $signed(a), m ? "-" : "+", $signed(b), $signed(s));
  endtask
  initial begin
    show(4'b0111, 4'b0101, 1);   // 7 - 5
    show(4'b0011, 4'b0101, 1);   // 3 - 5
    show(4'b0101, 4'b1101, 1);   // 5 - (-3)
    show(4'b0110, 4'b1001, 1);   // 6 - (-7): overflow
    show(4'b0110, 4'b0011, 0);   // 6 + 3: overflow
    // exhaustive check of all 512 cases
    for (int i = 0; i < 16; i++)
      for (int j = 0; j < 16; j++)
        for (int k = 0; k < 2; k++) begin
          a = i; b = j; m = k; #1;
          if (s !== 4'((k ? i - j : i + j) & 15)) errors++;
        end
    $display("exhaustive check: %0d errors", errors);
  end
endmodule

Output (Icarus Verilog with -g2012):

0111 - 0101 = 0010  C4=1 V=0   unsigned  7 -  5 ->  2   signed  7 -  5 ->  2
0011 - 0101 = 1110  C4=0 V=0   unsigned  3 -  5 -> 14   signed  3 -  5 -> -2
0101 - 1101 = 1000  C4=0 V=1   unsigned  5 - 13 ->  8   signed  5 - -3 -> -8
0110 - 1001 = 1101  C4=0 V=1   unsigned  6 -  9 -> 13   signed  6 - -7 -> -3
0110 + 0011 = 1001  C4=0 V=1   unsigned  6 +  3 ->  9   signed  6 +  3 -> -7
exhaustive check: 0 errors

Read the lines carefully, because they show every rule of this chapter:

  • 7 − 5: result 0010, C4 = 1 (no borrow), V = 0. Correct both as unsigned and signed.

  • 3 − 5: result 1110. As unsigned it reads 14 and C4 = 0 flags the borrow. As signed it is −2, correct, and V = 0.

  • 5 − (−3): the true answer +8 does not fit in 4-bit signed (range −8 to +7), so V = 1 and the bits read −8.

  • 6 − (−7) = +13 also overflows (V = 1). 6 + 3 = +9 overflows in addition mode.


Full Subtractor vs Adder-Subtractor

Point

Ripple-borrow subtractor

Adder + 2's complement

Building block

n full subtractors

n full adders + n XOR gates

Can also add?

No

Yes (M = 0)

Unsigned "A < B" indicator

Final borrow = 1

Final carry = 0

Signed overflow

Bn ⊕ Bn−1 (borrow into vs out of the sign bit)

Cn ⊕ Cn−1

Used in practice

Rarely (teaching, special circuits)

Every ALU


Common Mistakes

  • Writing Bout = AB′. A borrow is needed when A is 0 and B is 1: Bout = A′B. Always check the row A = 0, B = 1.

  • Thinking the difference is different from the sum. D = A ⊕ B ⊕ Bin is exactly the full adder's sum.

  • Forgetting the +1. Inverting B gives the 1's complement; you must also set C0 = 1 to get A − B. Without it you compute A − B − 1.

  • Reading Cout = 1 as "borrow" after A + B′ + 1. It is the opposite: carry out 1 means no borrow.

  • Using Cout for signed overflow. For signed numbers use V = Cn ⊕ Cn−1; Cout is only for unsigned results.

  • Building the full subtractor from two half subtractors in the wrong order. HS2 must compute D1 − Bin, not Bin − D1.


GATE and Interview Questions

Q1. Write the expressions for the difference and borrow of a full subtractor.

D = A ⊕ B ⊕ Bin = Σm(1, 2, 4, 7); Bout = A′B + A′Bin + BBin = Σm(1, 2, 3, 7).

Q2. How can a full adder be converted into a full subtractor?

The difference is the same as the sum, so keep S. For the borrow, the carry logic must see A′ instead of A: Bout(A, B, Bin) = Cout(A′, B, Bin). So one inverter on A, feeding only the carry logic, does it.

Q3. In the adder-subtractor, what are the XOR gates for, and what is C0?

Each XOR passes Bi unchanged when M = 0 and inverts it when M = 1 (a controlled inverter). C0 = M adds the 1 needed to turn the 1's complement into the 2's complement during subtraction.

Q4. A 4-bit adder-subtractor in subtract mode computes 0100 − 0110. Give the result bits, C4 and V.

0100 + 1001 + 1 = 0100 + 1010 = 1110, C4 = 0. Carries: C1 = 1, C2 = 0, C3 = 0, C4 = 0, so V = 0. Result 1110 = −2 as signed (4 − 6 = −2, correct); as unsigned, C4 = 0 signals a borrow.

Q5. How many 2-input NAND gates are needed for a half subtractor and a full subtractor?

5 for the half subtractor and 9 for the full subtractor, the same as the corresponding adders.

Q6. Why do processors not include a separate subtractor circuit?

Because A − B = A + B′ + 1 lets the existing adder subtract with only n XOR gates and the carry input. It saves area and gives one unified circuit (and one set of flags) for both operations.


Summary

  • Half subtractor: D = A ⊕ B, Bout = A′B (5 NAND gates).

  • Full subtractor: D = A ⊕ B ⊕ Bin, Bout = A′B + A′Bin + BBin = A′B + Bin(A ⊕ B)′ (9 NAND gates, or 2 half subtractors + OR).

  • Subtractor equations = adder equations with A complemented in the borrow logic.

  • Chaining full subtractors gives a ripple-borrow subtractor; final borrow 1 means A < B (unsigned).

  • In practice, A − B = A + B′ + 1: an adder with XOR gates on B and C0 = M forms the adder-subtractor. Carry-out 1 means no borrow; signed overflow is V = Cn ⊕ Cn−1.

  • Both ripple designs are slow for wide words; Ripple-Carry & Carry Look-Ahead Adders measures the delay and fixes it.