Subtraction Is Addition
In section 2.1 we built adders. This section builds the rest of the ALU, and it starts with subtraction. Suppose you have just finished a 4-bit ripple-carry adder and someone asks for a subtractor. You might expect to start again with a different circuit. You do not need to. The subtractor is the adder you already have, with four XOR gates on one input and one wire moved. That is not a lucky shortcut. Two’s complement was chosen precisely so that the same adder would do both jobs, and this article traces exactly how.
The identity
In two’s complement, the negative of $B$ is its bitwise complement plus one:
$$-B = \bar{B} + 1$$
So subtraction is
$$A - B = A + (-B) = A + \bar{B} + 1$$
Read that as an instruction: to subtract $B$, add the complement of $B$ and then add 1. Both parts are cheap. Inverting bits is a row of inverters. And adding 1 costs nothing at all, because a ripple-carry adder has a carry-in on its least significant bit that is normally tied to 0. For subtraction, set it to 1.
XOR as a controlled inverter
We want something that passes $B$ unchanged when adding and inverts it when subtracting. An XOR gate with a control signal on one input does exactly that:
| sub | B | output |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
With sub = 0 the output is $B$; with sub = 1 it is $\bar{B}$. Put one XOR on each bit of $B$, tie all their control inputs to the same sub signal, and also connect sub to the adder’s carry-in:
- sub = 0: the XORs pass $B$, carry-in is 0, the adder computes $A + B$.
- sub = 1: the XORs invert $B$, carry-in is 1, the adder computes $A + \bar{B} + 1 = A - B$.
One circuit, one control signal, two operations. Figure 1 shows it.
Example 1: 6 − 3
$A = 0110$, $B = 0011$. Invert $B$ to get $1100$ and add with carry-in 1:
| Bit | A | $\bar{B}$ | Cin | Sum | Cout |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 | 0 |
| 2 | 1 | 1 | 0 | 0 | 1 |
| 3 | 0 | 1 | 1 | 0 | 1 |
Result $0011 = 3$, with a carry out of 1. Correct.
Example 2: 3 − 6
$A = 0011$, $B = 0110$. We expect $-3$, which is $1101$ in 4-bit two’s complement. Invert $B$ to get $1001$:
| Bit | A | $\bar{B}$ | Cin | Sum | Cout |
|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 | 1 |
| 2 | 0 | 0 | 1 | 1 | 0 |
| 3 | 0 | 1 | 0 | 1 | 0 |
Result $1101 = -3$, carry out 0. The MSB is 1, so the result is negative, as expected.
Signed overflow
Signed overflow means the true result does not fit in the available bits. The test is the same as for addition: compare the carry into the most significant full adder with the carry out of it.
$$V = C_{in,MSB} \oplus C_{out,MSB}$$
If the two disagree, the sign bit has been changed by a carry that should not have reached it, or failed to reach it, and the result’s sign is wrong.
| $C_{in,MSB}$ | $C_{out,MSB}$ | V | Meaning |
|---|---|---|---|
| 0 | 0 | 0 | no overflow |
| 0 | 1 | 1 | overflow, result too large |
| 1 | 0 | 1 | overflow, result too small |
| 1 | 1 | 0 | no overflow |
Borrow in unsigned subtraction
For unsigned numbers the question is whether the subtraction went below zero, which is a borrow. The carry out of the MSB tells you, but inverted:
$$\text{Borrow} = \overline{C_{out}}$$
When $A \geq B$, the addition $A + \bar{B} + 1$ produces a carry out of 1: no borrow. When $A < B$ the carry out is 0: a borrow occurred. In example 1 the carry out was 1 and $6 \geq 3$; in example 2 it was 0 and $3 < 6$.
This inversion catches people out. After a subtraction, carry out 1 means the result did not go negative. It is the opposite sense from addition, where a carry out means the result was too big, and copying the addition check into a subtractor without adjusting it is a common bug.
Timing
The XOR layer adds one gate delay in front of the adder:
| Path | Delay |
|---|---|
| sub or B, through the XOR layer | 1 |
| through the four full adders on the carry chain | 8 |
| final sum XOR | 1 |
| total | 10 |
For comparison the plain 4-bit ripple-carry adder was about 10 as well when counted from its inputs; the XOR layer costs one gate delay for doubling what the circuit can do.
Practice Exercise
Problem 1. Compute $0101 - 1010$ with the adder/subtractor, trace it bit by bit, and check for overflow.
Solution
$A = 0101$ (+5), $B = 1010$ (−6 signed). $\bar{B} = 0101$, carry-in 1.
| Bit | A | $\bar{B}$ | Cin | Sum | Cout |
|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 |
| 2 | 1 | 1 | 0 | 0 | 1 |
| 3 | 0 | 0 | 1 | 1 | 0 |
Result $1011$, carry out 0. Carry into the MSB is 1, carry out is 0, so $V = 1$: overflow. The true answer is $5 - (-6) = 11$, which is outside the signed range −8 to +7, and the pattern $1011$ (−5) is meaningless. The overflow flag is the only warning you get.
Problem 2. For unsigned $A = 0010$ (2) and $B = 0111$ (7), compute $A - B$. What does the carry out tell you?
Solution
$\bar{B} = 1000$. $0010 + 1000 + 1 = 1011$ with carry out 0. Carry out 0 means a borrow: $2 - 7$ is negative and cannot be represented unsigned. The bits $1011$ read as 11, which is $2 - 7 + 16$, the wrapped result.
We now have a circuit that adds and subtracts. In the next article we finish it as a proper unit with the four status flags, test it against the cases that matter, and chain two of them into an 8-bit unit.