You were asked how you would compute a minus b with nothing but that adder and a way to flip bits. Today you find out the answer costs thirty two gates.
Collect their ideas first. Someone will say flip the bits. Do not confirm it yet.
One question runs through the hour, and the answer is smaller than anyone expects.
the hour in three questions
How much new hardware does subtraction cost? Write down a guess now. Most people say about another adder.
If not a subtractor, then what? You will have to decide what a negative number even is.
And what does the winning answer cost in gates and delays, judged the way you have judged everything since Class 21?
Get a number on the board for the guess. Two hundred gates is typical. The answer is thirty two.
take the honest route first
There is nothing wrong with just building a subtractor.
it works, and it is familiar
A borrow behaves exactly like a carry. One column makes a borrow, one passes it along, one stops it dead.
Which means it chains exactly like a carry did, and everything you learned in Class 21 and 22 applies unchanged.
Let them notice the borrow logic is the carry logic with the signs moved. That recognition is the point.
The trouble is not that it fails. It is that you now own two of everything.
remember
Two full width circuits, and the borrow chain needs its own lookahead network or it clocks at 0.77 GHz.
544 gates instead of 272, to do an operation the machine already almost does.
So before building it, ask whether the adder you already have could be made to do the job.
This is the cost-first move again. They should want a cheaper answer before you offer one.
THE MOVE OF THE HOUR
a − b = a + (−b)
Nothing about that is new. It is the first thing you were ever taught about subtraction.
But look at what it did to the problem. Subtraction was a question about circuits. Now it is a question about how you write a negative number.
Same shape as last session. Stop building, and look harder at the definition instead.
press step and watch it wrap
Your adder cannot count past its last column. It rolls over.
They have met this before. It was Class 21's worst case input, the one that set the clock.
Whatever you write for minus b, it has to make b plus it come out zero.
the only requirement, and it is a hard one
The adder must get the right answer without being told anything changed. No new gates, no mode, no sign handling.
Since it wraps at 232, the number that cancels b is whatever is left when you take b away from the wrap point.
Every candidate from here on gets tried against that one test.
Fix this test on the board. Sign magnitude and one's complement are about to fail it in different ways.
hands up first: will the adder get this right?
First candidate, and the one everybody suggests: use the top bit as a sign.
why it fails
The adder has no idea the top bit means anything special. It adds it like every other column, worth 231.
Five plus minus five comes out as minus ten. And there are two zeros, positive and negative.
You could fix it with extra logic, but that is exactly the second circuit you were trying to avoid.
Take the vote before revealing. Most will say it works, because it is how humans write negatives.
Second candidate, and much closer: just flip every bit of b.
so near
The signs now work. Positives and negatives add correctly nearly all of the time, with no extra logic.
But it lands one short, and it still has two zeros: all zeros and all ones.
The usual fix is to take the carry that falls off the end and add it back in, which is a second pass through the adder.
Take this one seriously. Real machines shipped with it. One short is a small crime and a fatal one.
THE ANSWER, AND WHY IT IS CHEAP
Flipping lands one short. So write the algebra out and see why.
The middle line is the one that matters: all ones minus b never borrows, so flipping is subtraction with no chain.
eight bits, on your own, before the reveal
Write minus five.
Then check it: add five to it and watch it wrap to zero. That check is the whole definition.
So what does it take to flip every bit, only when you want to?
remember
XOR with 1 flips a bit. XOR with 0 leaves it alone. So one control line into thirty two XOR gates does the whole job.
Thirty two gates, and one gate delay before the adder sees anything.
Let them derive the XOR trick from the truth table if there is time. It is two lines.
FOUR HOURS UNUSED
And the plus one? You have been carrying a spare input since Class 20.
remember
Column zero has a carry in. You have wired it to zero for four sessions because nothing ever carried into the first column.
Set it to one and the adder computes a + ~b + 1 with no new hardware at all. The plus one is free.
This is the delight of the hour. Let them see the input that has been sitting there doing nothing.
flip the control line and watch both change at once
One control line drives the flips and the carry in together.
control
Same adder, same lookahead network, nothing rebuilt. One wire decides which operation happens.
Now answer the question from the start of the hour.
judged the way you judge everything now
32 gates on top of 272, so about 12% more. One gate delay on top of twelve, so about 8% more.
260 ps against a 333 ps cycle. Still fits at 3 GHz, with a ceiling of 3.85 GHz.
Against the 544 gates and second lookahead network a real subtractor would have cost.
Put the guess from slide two back on the board next to thirty two. That contrast is the payoff.
one loose end, and it costs one more gate
Thirty two bits cannot hold every answer. How does the circuit know?
remember
If the carry going into the sign column and the carry coming out of it disagree, the answer did not fit.
One XOR gate, on two wires you already have. Checked on all sixty five thousand eight bit pairs.
Do not derive this formally. Show the two cases, state the rule, move on.
One more thing falls out that you did not ask for.
remember
Is a less than b? Subtract and look at the sign. Are they equal? Subtract and check for all zeros.
Class 21 listed every comparison as a user of the adder. This is why. A comparison is a subtraction.
Every if statement and every loop condition in every program they have written runs through this circuit.
Five down, three to go.
the export from this hour
When an operation looks expensive, try changing what the numbers mean before you change the circuit. Two's complement is a representation choice, not a piece of hardware.
And look for the input you are already paying for and not using. The carry in sat idle for four sessions.
The representation move returns for floating point, and again for signed comparison in the ISA.
How much did subtraction cost?
Thirty two XOR gates, one gate delay, and an input that was already there. Not because subtraction is easy, but because you stopped asking the circuit to change and asked the numbers to change instead.
Next session: you can add and subtract in one circuit at the same speed. Multiplication will not be nearly so generous.
Stop here. Send off: multiply 13 by 11 in binary, by hand, the way you would on paper. Count how many additions it took you. Bring the number.