Binary Subtraction

Introduction

Binary subtraction might seem like it would need a completely separate circuit from addition, but one of the most elegant insights in computer engineering is that subtraction can be performed using the same adder hardware with a simple modification. By representing negative numbers in two's complement form, subtraction becomes addition of a negative number. This unification of addition and subtraction into a single circuit is a cornerstone of digital arithmetic design and is used in every modern processor.

The key idea is this: to compute A - B, we instead compute A + (-B). In two's complement representation, -B is obtained by inverting all bits of B and adding 1. So subtraction requires only a bit inverter and the same adder used for addition — no separate subtractor circuit is needed.

Two's Complement Review

In an n-bit two's complement system, positive numbers are represented normally, and negative numbers are represented by their two's complement. To negate a number: invert all bits (one's complement) and add 1. For example, in 4 bits:

• +5 = 0101
• To find -5: invert → 1010, add 1 → 1011
• So -5 = 1011

This representation has the beautiful property that addition of positive and negative numbers works correctly without any special cases. The range for n bits is from -2^(n-1) to +2^(n-1) - 1. For 4 bits, that is -8 to +7.

The Adder-Subtractor Circuit

The combined adder-subtractor circuit uses XOR gates as conditional inverters. A control signal, typically called Sub or M (mode), determines whether the circuit performs addition or subtraction:

• When Sub = 0: each XOR gate passes B through unchanged (since B XOR 0 = B), and carry-in is 0. The circuit performs A + B.
• When Sub = 1: each XOR gate inverts B (since B XOR 1 = B'), and carry-in is set to 1. The circuit performs A + B' + 1 = A + (-B) = A - B.

The hardware is remarkably simple: take a standard ripple carry adder and add one XOR gate in front of each B input, with the Sub signal connected to the other XOR input. Connect the same Sub signal to the carry-in of the least significant bit. That is the entire modification — one XOR gate per bit and a single wire.

Worked Example

Let us subtract 3 from 7 using 4-bit two's complement (computing 7 - 3):

The carry-out of the MSB is 1, which in subtraction context means the result is positive (no borrow occurred).

Now let us compute 3 - 7 (a negative result):

The result 1100 has its MSB set, indicating a negative number. To verify: invert 1100 → 0011, add 1 → 0100 = 4. So the result is -4, which is correct.

Overflow Detection

Overflow occurs when the result of an arithmetic operation cannot be represented in the available number of bits. For two's complement subtraction (and addition), overflow is detected by examining the carry into and carry out of the most significant bit position.

The overflow condition is: Overflow = Cin(MSB) XOR Cout(MSB)

Overflow happens when:

• Subtracting a negative number from a positive number gives a negative result (positive overflow)
• Subtracting a positive number from a negative number gives a positive result (negative overflow)

For example, in 4 bits: 7 - (-5) should give 12, but 12 cannot be represented in 4-bit two's complement (max is 7). The circuit would produce an incorrect result and set the overflow flag.

Borrow Interpretation

In unsigned subtraction, the carry-out has a different meaning. If there is no carry-out (Cout = 0) when Sub = 1, it means a borrow has occurred — the result is negative in an unsigned sense, meaning B was larger than A. Processors typically compute the borrow flag as the complement of the carry-out during subtraction. This is why the x86 architecture's carry flag represents borrow after a SUB instruction.

The Role of Flags in the ALU

When the ALU performs subtraction, it sets several condition flags that subsequent instructions can test:

• Zero flag (Z): Set if the result is all zeros (A equals B)
• Sign flag (S): Set to the MSB of the result (negative in signed interpretation)
• Carry flag (C): Inverted carry-out (represents borrow in subtraction)
• Overflow flag (V): XOR of the last two carries (signed overflow)

These flags enable comparison operations: a CMP instruction is simply a subtraction that discards the result but keeps the flags. Conditional branches then test these flags.

Multi-Precision Subtraction

When numbers are wider than the ALU's word size, subtraction must be performed in multiple steps. The processor subtracts the least significant words first, then uses the "subtract with borrow" instruction (SBB on x86) for subsequent words. SBB accounts for any borrow from the previous stage by subtracting the carry flag from the result.

For example, subtracting two 64-bit numbers on a 32-bit ALU:

1. Subtract the lower 32 bits (SUB instruction) — sets the carry/borrow flag
2. Subtract the upper 32 bits with borrow (SBB instruction) — incorporates the borrow from step 1

Comparison with One's Complement

An alternative representation is one's complement, where negation means simply inverting all bits (no +1 step). One's complement subtraction is simpler in some ways but has the problem of "negative zero" (all 1s) and requires end-around carry — if there is a carry-out, it must be added back to the result. Two's complement eliminated these complications, which is why virtually all modern hardware uses it.

Key Takeaways

1. Binary subtraction is performed using the same adder hardware as addition, with XOR gates to conditionally invert the subtrahend
2. The adder-subtractor circuit uses a single control signal (Sub) to switch between A+B and A-B
3. Two's complement representation makes this possible: A - B = A + (NOT B) + 1
4. Overflow is detected by XORing the carry-in and carry-out of the MSB
5. The carry-out during subtraction indicates whether a borrow occurred (inverted for unsigned interpretation)
6. Condition flags (Zero, Sign, Carry, Overflow) set during subtraction enable comparison and conditional branching
7. This unified design means processors need only one arithmetic circuit for both addition and subtraction