I remember taking the digital systems course in my second year of university and being exposed to concepts like kmaps, 1s and 2s complement arithmetic. These building blocks served as the foundations for bigger concepts like adders, halfadders, comparators, gates and what not.
It was pretty much fun doing the calculations then even though I didn’t fully realize why I needed to add a 1 while doing 1s complement arithmetic. Until I stumbled upon the excellent explanation in Charles Petzold’s Code; a great book that uses very lucid metaphors for explaining computing concepts. As is usually the case – the best explanations are typically so simple and straightforward that anyone can grasp them.
Even if you already know about 1s and 2s complement arithmetic; still go ahead and read this, you might find something interesting.
Subtraction – the basics
Assuming you need to find the difference between two numbers, e.g. 173 and 41; this is pretty straightforward, you do so
minuend  174 
subtrahend  041 
difference  133 
Aside: Minuend and subtrahend are valid names, the names of parameters for mathematical operations are given below.
















This is the simple case, how about the carry scenario when you need to ‘borrow’ from preceding digits?
minuend  135 
subtrahend  049 
difference  086 
Aha the pesky borrowing! What if there was a way to avoid borrowing? The first thing to think of is the ceiling of all 3digit numbers i.e. the smallest possible number that would require no borrows for any 3digit number. We use 3digits since we are taking a 3digit example; were the subtrahend to be a 5digit number, we would need the smallest 5digit number value too.
That smallest ‘noborrowsrequired’ number is 999. Unsurprisingly, it is the maximum possible value in base ten if you have only 3 digits to use in the hundreds, tens and units positions. Note: In other bases, the values would also be the penultimate value e.g. for base 8, it’ll be 777.
Now, let’s use this maximum value as the minuend
minuend  999 
subtrahend  049 
difference  950 
Since we are using 999 as the reference value, then 49 and 950 are complements of each other; i.e. both add up to give 999. So we can say 49 is the 9s complement of 950 just as 950 is the 9s complement of 49.
Awesome! We can now avoid the annoying carries!! But knowing this is useless in itself unless we can find some way to leverage this newfound knowledge. Are there math tricks to use? Turns out this is very possible and straightforward.
Mathfu?
Lets do some more maths tricks (remember all those crafty calculus dy/dx tricks)…
135 – 49 = 135 – 49 + 1000 – 1000
= 135 + 1000 – 49 – 1000
= 135 + 1 + 999 – 49 – 1000
= 135 + 1 + (999 – 49) – 1000
= 136 + 950 – 1000
= 1086 – 1000
= 86
QED!
What’s the use of such a long process?
We just found a very long way to avoid carries while doing subtraction. However, there is no motivation to use this since it is quite inefficient in base 10. So what’s the reason for all this?
It turns out that in computerland, counting is done in 0s and 1s. The folks there can’t even imagine there are numbers other than 1 and 0. As you’ll see, there are some great advantages to using the 1s complement approach in this area.
Lets take a simple example e.g. 11 – 7
minuend  1011 
subtrahend  0111 
difference  ???? 
Applying the same trick again (this time the minuend will be 1111 instead of 9999).
minuend  1111 
subtrahend  0111 
difference  1000 
Do you notice a pattern between the subtrahend (0111) and the difference (1000)? The complements seem to be ‘inverses’ of each other.
The 1s complement of any numeric binary value is just the bitwise inverse of the bits in the original value. Calculation is just a matter of flipping each bit’s value, a linear O(n) operation that can be quite fast. That’s a BIG WIN.
Continuing the process again with the addition step this time:
Augend (difference from step above)  01000 
Addend (of 1)  00001 
Addend (of original 11 value)  01011 
Sum  10100 
Finally the subtraction of the next 1* number that is larger which will be 10000 (since we used 1111).
subtrahend  10100 
minuend  10000 
difference  00100 
And there is the 4! answer done!
How about negative numbers? Simple, just do the same process and invert the answers.
Hope you found this fascinating and enjoyed it. Let me know your thoughts in the comments.
0 Comments
·Leave a Reply