I just finished a discrete mathematics class here at UCSD, and part of the course was on number systems. I want to share a very interesting technique I invented for taking the complements of numbers, which I and my classmates have found immensely helpful.
Why number complements? Number complements are important because they allow us to do subtraction through addition. This makes computers cheaper because they eliminate the need for extra hardware to perform subtraction. If you already know what complements are or just want to see the magic rainbow table in action, feel free to skip to the Rainbow Table section.
There are two complements for binary numbers: ones’ complement and two’s complement.
Ones’ complement is defined as
2k - x - 1, where
k is the number of digits and
x is the positive number you want the negative version of. Interestingly, this can be easily found by “flipping” all the digits in the original positive binary number. (We’ve known this for years.) Make all
0s, and all the
1s. For example, the ones’ complement of
0101 (5) is
1010 (-5 in ones’ comp). Ones’ complement is nice since it allows us to subtract through addition, but there are a few small problems with it. First, if you take the binary representation of
0000 if we have 4 digits) and take its one’s complement, you get
-0. This doesn’t really make sense, since there is no negative zero. Second, the addition is a bit more involved than we optimally would like, because you have to add the carry-out digit back on the other side. For example, let’s say you want to subtract 2 from 3 in ones’ complement binary with 4 bits. You have:
111 0011 (3) +1101 (-2, one's complement of 2 in binary: 0010) 10000
Everything has to happen inside the 4 digits, so the extra digit on the end is ignored in the final result, but in order to get the proper result in ones’ complement, the carry out digit has to be added back on the other side of the number. That gives us:
0000 + 1 0001
0001 is 1 in binary, which is what we would expect since 3-2=1.
Two’s complement is the most widely used way to represent negative numbers in computers. The way you get two’s complement is by taking the value of ones’ complement and adding 1 to it. For example, the two’s complement of
0101 (5 in binary) is
1010 + 1, or 1011 (-5 in two’s comp). Two’s complement is better than one’s complement because it allows us to merely add numbers together and not worry about adding the carry out digit back on the other side. It does not have the problem of negative zero.
0000 flipped is
1111 + 1. Adding that gets us
10000, but we ignore the
1 since the number has to fit inside 4 digits. Let’s use the example of subtracting 2 from 3 again to demonstrate two’s complement. This time, you have:
11 0011 (3) +1110 (-2, two’s complement of 2 in binary: 0010) 10001
We ignore the carry out digit on the left and get
0001 as our answer, as expected.
The generalized version of binary’s ones’ complement is called the diminished radix complement, and the generalized version of binary’s two’s complement is called the radix complement. This comes from the fact that binary is a base 2, because radix is another word for a number system base.
The Rainbow Table
As it turns out, this idea of number complements goes beyond binary. In fact, it works with regular decimal numbers too! The only problem is, how do we “flip” the digits to get the complements for regular decimal numbers?
Enter my invention, the Rainbow Table.
(Not to be confused with the cryptographic rainbow table.)
List all the digits for the base you are working with (in the case of decimal, 0-9) vertically and divide it through the middle horizontally.
This rainbow table makes complements easy. To flip a digit, just find the digit in the table and follow its line to the corresponding flipped value. This gets you nines’ complement (the equivalent of binary’s ones’ complement). To get ten’s complement, just add 1 like we did earlier for binary’s two’s complement. Let’s look at the example of 60 – 40 to see ten’s complement in action:
At minimum, we need 3 digits (one digit needs to carry the sign of the number), so let’s pad the numbers with
Now, let’s transform -040 into ten’s complement using the rainbow table.
0 becomes 9 4 becomes 5 0 becomes 9
This gives us 959 as the 3 digit nines’ complement representation of -40. Adding
1 gives us
960 as the 3 digit ten’s complement representation.
Now, we can finally do the subtraction through addition.
1 060 (3) +960 1020
Since we are only working in 3 digits, we ignore the 1 on the end. This gives us
20) as the result, which is what we expected from 60 – 40! How cool is that?
Rainbow Tables and Other Number Bases
1s in binary is just a specialized case of a rainbow table with only 0 and 1:
All the number bases discussed so far have been even (i.e. base 2 and base 10). Base 3 (ternary) is an example of an odd base. Rainbow Tables for odd bases are pretty much the same as before, with one slight difference – the middle digit stays fixed in the flipping process. For example, this is a base 3 Rainbow Table:
While you’re not likely to find yourself needing to take the complements of numbers regularly (you’re probably faster at doing regular subtraction), it is still an interesting topic to explore. Rainbow tables make taking complements quite easy. Another interesting topic to think about is how to determine the sign of a number in a base other than binary. (It’s easy in binary, just look at the leftmost digit. If it is a 1, it’s negative. If it’s a 0, it’s positive.) But enough for this post – that would make a good subject for another time.