Code_ The Hidden Language of Computer Hardware and Software - Charles Petzold [51]
For this explanation, I need to refer to the two numbers being subtracted. Their proper names are the minuend and the subtrahend. The subtrahend is subtracted from the minuend, and the result is the difference:
To subtract without borrowing, you first subtract the subtrahend not from the minuend but from 999:
You use 999 here because the numbers have 3 digits. If the numbers had 4 digits, you would use 9999. Subtracting a number from a string of 9s results in a number called the nines' complement. The nines' complement of 176 is 823. And it works in reverse: The nines' complement of 823 is 176. What's nice is this: No matter what the subtrahend is, calculating the nines' complement never requires a borrow.
After you've calculated the nines' complement of the subtrahend, you add it to the original minuend:
And finally you add 1 and subtract 1000:
You're finished. The result is the same as before, and never once did you borrow.
Why does this work? The original subtraction problem is
253 – 176
If any number is both added to and subtracted from this expression, the result will be the same. So let's add 1000 and subtract 1000:
253 – 176 + 1000 – 1000
This expression is equivalent to
253 – 176 + 999 + 1 – 1000
Now the various numbers can be regrouped, this way:
253 + (999 – 176) + 1 – 1000
And this is identical to the calculation I demonstrated using the nines' complement. We replaced the one subtraction with two subtractions and two additions, but in the process we got rid of all the nasty borrows.
What if the subtrahend is larger than the minuend? For example, the subtraction problem could be
Normally, you would look at this and say, "Hmmm. I see that the subtrahend is larger than the minuend, so I have to switch the two numbers around, perform the subtraction, and remember that the result is really a negative number." You might be able to switch them around in your head and write the answer this way:
Doing this calculation without borrowing is a little different from the earlier example. You begin as you did before by subtracting the subtrahend (253) from 999 to get the nines' complement:
Now add the nines' complement to the original minuend:
At this point in the earlier problem, you were able to add 1 and subtract 1000 to get the final result. But in this case, that strategy isn't going to work well. You would need to subtract 1000 from 923, and that really means subtracting 923 from 1000, and that requires borrowing.
Instead, since we effectively added 999 earlier, let's subtract 999 now:
When we see this, we realize that our answer will be a negative number and that we really need to switch around the two numbers by subtracting 922 from 999. This again involves no borrowing, and the answer is as we expect:
This same technique can also be used with binary numbers and is actually simpler than with decimal numbers. Let's see how it works.
The original subtraction problem was
When these numbers are converted to binary, the problem becomes
Step 1. Subtract the subtrahend from 11111111 (which equals 255):
When we were working with decimal numbers, the subtrahend was subtracted from a string of nines, and the result was called the nines' complement. With binary numbers, the subtrahend is subtracted from a string of ones and the result is called the ones' complement. But notice that we don't really have to do a subtraction to calculate the ones' complement. That's because every 0 bit in the original number becomes a 1 bit in the ones' complement, and every 1 bit becomes a 0 bit. For this reason, the ones' complement is also sometimes called the negation, or the inverse. (At this point, you might recall from Chapter 11 that we built something called an inverter that changed a 0 to a 1 and a 1 to a 0.)
Step 2. Add the ones' complement of the subtrahend to the minuend:
Step 3. Add