Subtractors: Foundations — Hardware deep dive

Throughout this page, two abbreviations appear:

Symbol 0 — a bit (the atom of everything)

Picture it as a single lamp on the board. Every letter you will meet ( $A$ , $B$ , $D$ …) is one of these lamps — either dark or glowing.

Figure s01 — A bit as a lamp. Left: dark lamp = value $0$ . Right: glowing lamp = value $1$ . There is no in-between state; this "strictly on-or-off" fact is what makes truth tables finite and buildable.

Why the topic needs it: subtraction of "binary numbers" means subtraction of columns of bits. If you don't picture each letter as a lamp that is strictly on-or-off, the truth tables below look like magic. They are not — they are just "try every possible pattern of lamps."

Symbols $A$ and $B$ — the two inputs of one column

Picture two lamps stacked vertically, exactly like the two digits you line up on paper when you do subtraction by hand.

The borrow idea (before any symbol for it)

Do $3 - 5$ in your head. You can't — $3$ is smaller. On paper you'd "borrow from the next column." The same thing happens with single bits: $0 - 1$ can't stay $0 - 1$ , so we grab value from the column above.

Figure s02 — Borrowing in one column. The top bit is $A = 0$ , the bottom is $B = 1$ , so $0 - 1$ is impossible. We pull a bundle worth $2$ (yellow arrow) from the higher column, compute $0 + 2 - 1 = 1$ giving the difference $D = 1$ , and send a "you owe 1" flag upward (pink arrow): that flag is $B_{o u t} = 1$ .

Why the topic needs it: the entire difference between a subtractor and an adder is this one signal. An adder pushes a carry up; a subtractor pulls a borrow down. Same picture, opposite direction.

Symbol $B_{o u t}$ and $B_{in}$ — the borrow signals

Why the topic needs it: the HS ignores incoming borrow (no $B_{in}$ ). The FS accepts $B_{in}$ so it can be chained. That single extra input is the only structural difference between the two circuits.

Symbol $D$ — the difference output

Picture: after you took $B$ (and any borrow) away from $A$ , whatever glows in the current column is $D$ .

The bar: $\overset{ˉ}{A}$ means NOT

$\overset{ˉ}{0} = 1 \overset{ˉ}{1} = 0$

The bar can also sit over a whole expression, not just one letter. For example $\overline{A \oplus B}$ means "first compute $A \oplus B$ , then flip the result." So $\overline{A \oplus B} = 1$ exactly when $A$ and $B$ are the same (because $A \oplus B$ is $1$ when they differ, and the bar flips that).

Why the topic needs it: the borrow only happens when the top bit is $0$ . But formulas multiply things that are true ( $= 1$ ). So to say "top bit is 0" as a $1$ -signal, we write $\overset{ˉ}{A}$ — it equals $1$ exactly when $A = 0$ . That is why the borrow is $\overset{ˉ}{A} B$ and not $A B$ .

The dot and plus: AND ( $\cdot$ ) and OR ( $+$ )

Operator precedence — read a formula without guessing

So $\overset{ˉ}{A} B + B B_{in}$ is read as $((\overset{ˉ}{A}) \cdot B) + (B \cdot B_{in})$ — the bar hits only $A$ , each AND-group forms first, then OR joins them. A bar over a group, like $\overline{A \oplus B}$ , always needs the whole expression evaluated first because the bar sits over all of it.

Why the topic needs it: $B_{o u t} = \overset{ˉ}{A} B + \overset{ˉ}{A} B_{in} + B B_{in}$ literally reads "borrow if (top is 0 AND bottom is 1) OR (top is 0 AND borrow-in) OR (bottom is 1 AND borrow-in)." AND builds each condition; OR collects them.

The XOR sign: $\oplus$

$A$	$B$	$A \oplus B$
0	0	0
0	1	1
1	0	1
1	1	0

Figure s03 — XOR reads "1 when they differ." The four columns show every $(A, B)$ pair as two lamps; the output is $1$ (pink) only in the two middle cases where one lamp is on and the other off. This "1 when different" rule is exactly the difference bit $D$ .

Extending to three: $A \oplus B \oplus B_{in}$ is $1$ when an odd number of the three are $1$ . That is why the full-subtractor difference is a three-way XOR — it counts parity, and an odd count means one leftover candy.

Putting it together — the full truth tables and formulas

Now that every symbol is defined, here are the complete tables (no case left to the reader) and the boxed formulas they produce.

Half Subtractor (HS) — all 4 cases of $A - B$

$A$	$B$	$A - B$	$D$	$B_{o u t}$
0	0	$0$	0	0
0	1	borrow, leftover $1$	1	1
1	0	$1$	1	0
1	1	$0$	0	0

Reading the columns: $D = 1$ when the bits differ (that's XOR); $B_{o u t} = 1$ only in the row $A = 0, B = 1$ (that's $\overset{ˉ}{A} B$ ).

Full Subtractor (FS) — all 8 cases of $A - B - B_{in}$

$A$	$B$	$B_{in}$	$A - B - B_{in}$	$D$	$B_{o u t}$
0	0	0	$0$	0	0
0	0	1	$- 1$	1	1
0	1	0	$- 1$	1	1
0	1	1	$- 2$	0	1
1	0	0	$1$	1	0
1	0	1	$0$	0	0
1	1	0	$0$	0	0
1	1	1	$- 1$	1	1

$D$ is $1$ in every row where an odd number of inputs are $1$ — that is three-input XOR. $B_{o u t}$ is $1$ in every row where a borrow is needed. Grouping those five borrow-rows gives the standard sum-of-products form.

The shortcut $A - B = A + \overset{ˉ}{B} + 1$ — derived here, step by step

Real hardware doesn't build a separate subtractor; it reuses an adder. The claim is: $A - B = A + \overset{ˉ}{B} + 1 (mod 2^{n})$

Let us derive it rather than quote it. Every step is a WHAT / WHY.

Step 1 — What is $\overset{ˉ}{B}$ as a number? For an $n$ -bit value, flipping every bit turns $B$ into $(2^{n} - 1) - B$ . Why: the all-ones $n$ -bit number equals $2^{n} - 1$ , and flipping $B$ is the same as computing all-ones minus $B$ bit by bit (no borrow ever, since each column is $1 - B_{i}$ ). So: $\overset{ˉ}{B} = (2^{n} - 1) - B$

Step 2 — Add the $+ 1$ . Why: we want a clean $2^{n} - B$ (the "two's complement" of $B$ ), and Step 1 gave us one short of that. $\overset{ˉ}{B} + 1 = (2^{n} - 1) - B + 1 = 2^{n} - B$

Step 3 — Add $A$ . Why: our goal is $A - B$ , so start from $A$ and add the quantity from Step 2. $A + \overset{ˉ}{B} + 1 = A + (2^{n} - B) = 2^{n} + (A - B)$

Step 4 — Drop the $2^{n}$ . Why: $2^{n}$ is one bit wider than our $n$ -bit result; it lands in bit position $n$ , which our $n$ -bit output cannot hold, so it falls off. Discarding it is precisely what " $(mod 2^{n})$ " means (keep only the low $n$ bits). $A + \overset{ˉ}{B} + 1 (mod 2^{n}) = A - B$

The $2^{n}$ and $(mod 2^{n})$ notation, precisely

How the pieces feed the topic

Equipment checklist

Recall Self-test: can you answer each before moving on?

A bit can take which values? ::: Only $0$ or $1$ . What do HS and FS stand for? ::: Half Subtractor (no borrow-in) and Full Subtractor (with borrow-in $B_{in}$ ). In $A - B$ , which letter is the top (subtracted-from) bit? ::: $A$ . What does $\overset{ˉ}{A}$ equal when $A = 0$ ? ::: $\overset{ˉ}{A} = 1$ (NOT flips it). What does the overbar physically signal in a borrow formula? ::: "The top bit is $0$ " expressed as a $1$ -signal — the boss is broke. $B$ vs $B_{o u t}$ vs $B_{in}$ — which one is the bottom input operand? ::: Plain $B$ ; the others are borrow flags going up ( $B_{o u t}$ ) and coming in ( $B_{in}$ ). In boolean algebra, what does $+$ mean and what is $1 + 1$ ? ::: OR; $1 + 1 = 1$ . What does $A \cdot B$ (or $A B$ ) mean? ::: AND — true only when both are $1$ . Which binds tightest: NOT, AND, or OR? ::: NOT (the bar) binds tightest, then AND, then OR. Does $\overset{ˉ}{A} B$ mean $(NOT A) \cdot B$ or $NOT (A \cdot B)$ ? ::: $(NOT A) \cdot B$ — the bar covers only what it sits on. $A \oplus B$ equals $1$ in which case? ::: When $A$ and $B$ differ. Half-subtractor formulas? ::: $D = A \oplus B$ and $B_{o u t} = \overset{ˉ}{A} B$ . Full-subtractor formulas? ::: $D = A \oplus B \oplus B_{in}$ and $B_{o u t} = \overset{ˉ}{A} B + \overset{ˉ}{A} B_{in} + B B_{in}$ . Why is the difference bit $D = A \oplus B$ ? ::: Leftover is $1$ exactly when the two bits differ — the definition of XOR. What does " $(mod 2^{n})$ " throw away? ::: Any value at or above $2^{n}$ — the bit in position $n$ (a carry, not a borrow) — keeping only the low $n$ bits. Derive $A - B = A + \overset{ˉ}{B} + 1$ : what is $\overset{ˉ}{B}$ as a number? ::: $\overset{ˉ}{B} = (2^{n} - 1) - B$ , so $\overset{ˉ}{B} + 1 = 2^{n} - B$ , and $A + (2^{n} - B) = 2^{n} + (A - B)$ ; drop the $2^{n}$ .