Subtraction and the Adder-Subtractor

Subtract with an adder: invert b, add one, and read the carry and overflow flags the right way.

You Will Be Able To

  • Compute a − b as a + ~b + 1.
  • Build one adder that adds or subtracts under a mode bit.
  • Read the carry out of a subtraction as "no borrow".
  • Detect signed overflow in a subtraction.
Lesson
G4.7
Time
25 min
Runs on
Your browser
Check
5 questions

A level sensor reports how far a tank is below its mark: mark − level. Each reading is one unit short. The subtractor inverts the level and adds it, but nobody adds the 1.

Subtracting Without the + 1a = 100 in every step; b grows by 20. got is a + ~b, want is a − b.
0123b30507090got6949299want70503010one short
Scroll horizontally ↔
  1. Cycle 0

    100 − 30 should be 70. Inverting 30 gives −31 in two's complement, so the adder computes 100 − 31 = 69.

  2. Cycle 3

    Every result is exactly one short. The error never grows, which is why it hides in a quick test.

Measured on the simulator with 8-bit values.

A − b Is a + ~b + 1

In two's complement, −b = ~b + 1: invert every bit, then add one (lesson G1.2). So a − b = a + ~b + 1. An adder can subtract if you give it the inverted b and a carry in of 1.

Subtract With the Adder
23
22
21
20

Weights show bit magnitudes. For signed values, the leftmost bit has a negative weight.

Unsigned
5
Two’s complement
5

Carry chain (out → in): 1 1 0 1 1

Subtract operand B

23
22
21
20

Result: 0010 (2 signed)

Carry 1 Borrow 0 (carry means no borrow) Overflow 0

The signed result fits in this width.

Click any bit of a or b. The widget adds a and the inverted b with a carry in of 1, and shows the carry, borrow and overflow.

One Adder, an XOR Row and a Mode Bit

XOR with a control bit is a controlled inverter (lesson G2.7). Put one XOR on each b input, all driven by a mode bit sub. Feed the same sub into the adder's carry in.

An Adder-SubtractorThe mode bit drives an XOR on every bit of b, and the carry in of the adder.
  • I/O
  • Datapath
  • Data
  • Control
CallValueReturnWaiting
An adder-subtractorThe mode bit drives an XOR on every bit of b, and the carry in of the adder. io a N bits io b N bits io sub mode bit datapath XOR row bx = b ⊕ sub datapath Adder a + bx + cin io r, c, v result and flags abinvert?bxcinsum
  1. io bN bits
    • b → XOR row
  2. io submode bit
    • invert? → XOR row
    • cin → Adder
  3. datapath XOR rowbx = b ⊕ sub
    • bx → Adder
  4. datapath Addera + bx + cin
    • sum → r, c, v
  5. io r, c, vresult and flags
  6. io aN bits
    • a → Adder
  1. sub = 0: add

    Each XOR passes its b bit, and the carry in is 0. The adder computes a + b.

    Follow the calls, values and waits
    1. data 0011: XOR row → Adder
    2. data cin = 0: sub → Adder
  2. sub = 1: subtract

    Each XOR inverts its b bit, and the carry in is 1. The adder computes a + ~b + 1 = a − b.

    Follow the calls, values and waits
    1. data 1100: XOR row → Adder
    2. data cin = 1: sub → Adder
Read the diagram as text
  • a: N bits
  • b: N bits
  • sub: mode bit
  • XOR row: bx = b ⊕ sub
  • Adder: a + bx + cin
  • r, c, v: result and flags
  • a → Adder: a
  • b → XOR row: b
  • sub → XOR row: invert?
  • XOR row → Adder: bx
  • sub → Adder: cin
  • Adder → r, c, v: sum

One adder, N XOR gates and one wire from the mode bit to the carry in.

The cost of subtraction is N XOR gates. The + 1 costs nothing, because the adder already has a carry input.

Carry, Borrow and the Unsigned Compare

For unsigned numbers, the carry out of a + ~b + 1 is 1 exactly when a ≥ b. Then no borrow was needed. When a < b the carry out is 0, and the result wraps around.

Over all 256 pairs of 4-bit a and b, subtractingCount
Pairs with a ≥ b136
Pairs where the carry out is 1136
Pairs where "carry out = 1" equals "a ≥ b"256
Pairs where the signed result overflows64

Counted by a simulation of every pair. So the carry out of a subtraction is an unsigned compare for free.

Lesson G4.8 uses this: an unsigned a < b is just NOT carry out of a − b.

Overflow in a Subtraction

A signed subtraction overflows when the true result does not fit. That needs a and b of different signs, and a result whose sign differs from a. Subtracting a negative number from a positive one can give a result above the largest positive value.

The adder sees a and bx = ~b. So the add rule still works on the adder's own operands. Overflow is when a and bx have the same sign and the result has the other. An equal test is carry out XOR the carry into the top bit. Both agreed on all 256 subtractions of 4-bit numbers.

Operation (4 bits, signed)True resultrv
7 − (−1)81000 (−8)1
−8 − 1−90111 (7)1
3 − 5−21110 (−2)0

From the lab below. The range of four signed bits is −8 to 7.

Asked in interviews
  1. How do you subtract with an adder?

    Invert b with a row of XOR gates driven by a mode bit, and feed the same bit into the carry in. a + ~b + 1 is a − b in two's complement.

  2. What does the carry out mean after a subtraction?

    For unsigned numbers it is 1 when a ≥ b, so it means "no borrow". Borrow is its complement.

  3. When does a subtraction overflow?

    When a and b have different signs and the result has a different sign from a. Equally, when the carry out differs from the carry into the top bit.

Try It

Each line shows the signed operands, the signed result, the raw bits and the flags. 5 − 3 sets c (no borrow); 3 − 5 clears it.

7 + 1 and 7 − (−1) both overflow to −8. −8 − 1 overflows the other way, to 7.

Change the carry in to 0: write a + bx in place of a + bx + sub. Every difference is now one short.

Change v to use b in place of bx and run. Which lines change, and why?

RUNIcarus Verilog · in your browser
Edit the code, then run it
Expected: 5 - 3 = 2 r=0010 c=1 v=0 3 - 5 = -2 r=1110 c=0 v=0 7 + 1 = -8 r=1000 c=0 v=1 7 - -1 = -8 r=1000 c=0 v=1 -8 - 1 = 7 r=0111 c=1 v=1 0 - 0 = 0 r=0000 c=1 v=0
Read included file: tb.sv
// tb.sv: six operations, printed as signed numbers with the raw result and the flags (read-only).
module tb;
  logic [3:0] a, b, r;
  logic       sub, c, v;
  addsub4 dut (.a(a), .b(b), .sub(sub), .r(r), .c(c), .v(v));
  task automatic op(input logic [3:0] x, y, input logic s);
    a = x; b = y; sub = s;
    #1 $display("%3d %s %3d = %3d   r=%b c=%b v=%b", $signed(x), s ? "-" : "+", $signed(y), $signed(r), r, c, v);
  endtask
  initial begin
    op(4'd5, 4'd3, 1);
    op(4'd3, 4'd5, 1);
    op(4'd7, 4'd1, 0);
    op(4'd7, -4'd1, 1);
    op(-4'd8, 4'd1, 1);
    op(4'd0, 4'd0, 1);
  end
endmodule

Check Yourself

Spot the bugEach option is the body of an always_comb block of an 8-bit adder-subtractor with carry out c. The bench tries 400 seeded operations. Which body fails?
ConceptAn 8-bit adder-subtractor computes 20 − 30 as unsigned numbers. What are the carry out and the result?
ConceptWhich 4-bit signed subtraction overflows?
ConceptHow many XOR gates does an N-bit adder-subtractor add to an N-bit adder?
Predict the outputPredict the exact line: a 4-bit 3 − 5 done as 3 + ~5 + 1, printed in binary.
module tb;
  logic [3:0] a = 4'd3, b = 4'd5;
  initial $display("%b", 4'(a + ~b + 4'd1));
endmodule

Common Mistakes

Wrong Invert b and forget the + 1.

a + ~b is a − b − 1, the ones' complement result. Every difference comes out one too small, as in the hook.

Fix Feed the mode bit into the adder's carry in. On subtract it supplies the + 1 for free.

Wrong Read the carry out of a subtraction as a borrow.

The carry out is 1 when a ≥ b, that is, when no borrow is needed. It was so for all 256 pairs of 4-bit numbers.

Fix Borrow = NOT carry out. Some processors store the borrow in their flag and some store the carry, so read the manual.

Wrong Check overflow of a subtraction with the signs of a and b as for an add.

The adder really adds a and ~b. A subtraction overflows when a and b have different signs and the result differs from a.

Fix Use the signs of the adder's own operands, a and the inverted b. Or use carry out XOR the carry into the top bit.

Wrong Build a separate subtractor beside the adder.

It doubles the area. The XOR row and the carry in turn one adder into both.

Fix Share one adder; let the mode bit drive the XOR row and the carry in.

Remember

  • a − b = a + ~b + 1: invert b, and use the carry in for the + 1.
  • One adder adds or subtracts: an XOR row on b and the carry in, both driven by the mode bit.
  • After a subtraction, carry out = 1 means a ≥ b (unsigned): no borrow.
  • A subtraction overflows when a and b differ in sign and the result differs from a.

Practice

Report a problem with this page