Asked in Math and Arithmetic
Why is binary subtraction referred to as the invert-add-shift-add method?
January 31, 2013 7:07PM
This is because the given term refers to the method by which it works. You can subtract binary numbers in the way we're taught to do it in grade school, but computers do it using a different technique.
For example, let's say you're subtracting one number from another. We'll call them B and A respectively. The way this technique works is as follows:
- Take the complement of the number being subtracted (see footnote)
- Add it to the other number
- Remove the first digit of the result, and add it to the last digit
So we'll start by picking a couple of binary values for A and B:
A = 10110101
B = 101001
They must have the same number of digits, so we'll pad the front of B with zeros:
B = 00101001
Now take its complement:
B' = 11010110
Now add them together:
And remove the leftmost digit of the result, adding it to the resulting number:
10001011 + 1 = 10001100
Giving us the result. If you want to double check that, just add the result to the number we subtracted in the first place:
And you can see that this is our original value for A.
This is where that name comes from. First we "invert" the number we're subtracting by taking its complement. Next we "add" it to the first number. Then we "shift" the leftmost digit of the result over to the right end, and "add" it to the rightmost digit.
It is important to note that this is not unique to binary numbers. You can apply this to subtraction in any base. For example, let us subtract the decimal number 2343 from 14555:
We start by expanding 2343 to five digits by preceding it with zeros:
Now we take its complement:
And add that to the number from which we're subtracting:
Then we take the leftmost digit and add it to the remaining number:
And again, we can double check our answer:
2343 + 12212 = 14555
Demonstrating that this technique works.
The complement of a number is another number in which each digit, when added to the corresponding digit in the original number, will give us the largest available single-digit value in the base we're working in. For example, in regular decimal notation, the complement of 12345 is 87654, because each corresponding pair of digits (8 + 1, 7 + 2, 6 + 3, etc.) adds up to 9, the largest single digit value in decimal. Similarly, in hexadecimal, the complement of of 12345 would be EDCBA, and the binary complement of "11011" would be "00100".