I remember taking the digital systems course in my second year of university and being exposed to concepts like k-maps, 1s and 2s complement arithmetic. These building blocks served as the foundations for bigger concepts like adders, half-adders, 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 3-digit numbers i.e. the smallest possible number that would require no borrows for any 3-digit number. We use 3-digits since we are taking a 3-digit example; were the subtrahend to be a 5-digit number, we would need the smallest 5-digit number value too.
That smallest ‘no-borrows-required’ 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 new-found knowledge. Are there math tricks to use? Turns out this is very possible and straightforward.
Math-fu?
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 computer-land, 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.
CodeKraft 
One thought on “A simple explanation of 1s complement arithmetic”