We can represent numbers in binary; we can define the operations of binary arithmetic in terms of boolean logic; and we can implement boolean logic with digital electronics. Without that, computers would (at best) be very different than they are today...
1*104 + 2*103 + 5*102 + 7*101 + 3*100
It turns out that there's absolutely nothing sacred about our choice of 10 for a number radix -- a few cultures have used five, pre-Columbians in Central America (the Mayans, for instance) used 20, and the ancient Babylonians used 60 (we've inherited our system of dividing circles into degrees, minutes, and seconds from this). I've seen the claim that the Hebrews used 10 for some purposes and 12 for others, but haven't been able to verify it (but notice that our division of the day into hours apears to be a vestige of a duodecimal numbering system). So, instead of 10, we could use 8, 16, 79, 13... as we please.
In general, we can define any integer number radix r greater than 1 we want: the digits go from 0 to r-1, and the base is r (so it's 10 for decimal, 2 for binary, 8 for octal, 16 for hexadecimal, and so forth).
Let's take a number like 54 10 (that's 5*101 + 4*100). It's easy to verify that 54 = 3*16 + 6, or 3*161 + 6*160. Notice that this has the same form as we used above to ``decode'' a number in radix 10; this tells us that 54 10 = 36 16 . And, it turns out that there is a simple algorithm for converting numbers between any two radixes. We'll get to that in a minute.
A spectacularly useful radix for our purposes is binary: base 2. This is because (as I said at the start)
Let's take a look at a number like 3710. The first number less than or equal to 37 that is a power of 2 is 32 -- that's 25. So 37 = 32 + 5. The first number less than or equal to 5 that's a power of 2 is 4, so 3710 = 32+4+1. 1 is a power of 2, so 37 is
1*25 + 0 * 24 + 0 * 23 + 1 * 22 + 0 * 21 + 1 * 20,which we'll write as
1000112
1111 01101010 +01011001 --------- 11000011
3-input lookup table
| Inputs | Outputs | |||
|---|---|---|---|---|
| C in | X | Y | S | C out |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Hey! Easily defined in terms of logic!
Cout = (Cin and X) or (Cin and Y) or (X and Y)
So, we've seen that binary is a good radix to use in a computer. But, to say the least, it's not very convenient for us - writing all those 1's and 0's gets very tedious, very quickly. Fortunately, we can use another radix for our work, which is convenient for us (though not as convenient as decimal!), and also easily converted to binary.
Notice that in a binary number, a group of four bits (this is called a nybble, by the way) can represent a value from 0 to 15. Also, notice that if we divide a number into nybbles, the nybbles start at the 160, 161, 162, ... 16n positions. In other words, nybbles act just like digits in radix 16! That's great - it means we can divide a number up into nybbles, translate each nybble, and have a radix 16 number. More compact to write, easy to translate. Consequently, we write in hexadecimal almost exclusively when we're looking at hardware.
We can see a slight problem with this scheme if we translate 43 into hexadecimal: we get 2*161 + 11*160. But if we look at the number 21116, how can we tell whether it's supposed to be 2*161 + 11*160, or 2*162 + 1*161 + 1*160?
The solution is that we need to come up with some more digits. The convention is to use letters of the alphabet for the numbers from 10 to 15, giving us:
| Decimal | Binary | Hexadecimal |
|---|---|---|
| 0 | 0000 | 0 |
| 1 | 0001 | 1 |
| 2 | 0010 | 2 |
| 3 | 0011 | 3 |
| 4 | 0100 | 4 |
| 5 | 0101 | 5 |
| 6 | 0110 | 6 |
| 7 | 0111 | 7 |
| 8 | 1000 | 8 |
| 9 | 1001 | 9 |
| 10 | 1010 | a |
| 11 | 1011 | b |
| 12 | 1100 | c |
| 13 | 1101 | d |
| 14 | 1110 | e |
| 15 | 1111 | f |
One little thing - remember that hexadecimal is a shorthand we use. All numbers internal to the computer are really binary.
We start by looking at what happens when we divide a decimal number by 10. For an example, we'll use 12,573. If we divide it by 10 we get 1,257, with a remainder of 3. The remainder of the division is the least significant digit of the original number. If we divide 1,257 by 10, we get 125 with a remainder of 7 This gave us the next digit. If we keep dividing by the radix, each remainder in turn is another digit.
Let's take our 37 10 and see what happens when we do a bunch of divisions by 2. A convenient way to show this is with a table, where we have one column for the current number we're working with, another column for the result of dividing that number by the radix, and a third column for the digits we obtain. When we start, we'll just have the number we want to convert in the upper left corner, like this:
| Old | New | Digit |
|---|---|---|
| 37 | ||
We fill in the table row by row: we divide the number in the
Old column by the new radix (2 in this case), and put
the quotient in the New column and the remainder in
the Digit column. If the quotient is non-zero, we start
a new row, copying from the New column of the old row
to the Old column of the new row. When we're done,
the table looks like this:
| Old | New | Digit |
|---|---|---|
| 37 | 18 | 1 |
| 18 | 9 | 0 |
| 9 | 4 | 1 |
| 4 | 2 | 0 |
| 2 | 1 | 0 |
| 1 | 0 | 1 |
Since we obtained the results starting from the least significant digit, we read it starting at the bottom of the rightmost column of the table and working up, and the result is 1001012
This algorithm for converting a number from decimal to binary is called the division algorithm, because we divide on every step. In general, we can convert from decimal to any radix we want using this algorithm, dividing by our intended radix on every step.
| Old | Digit | New |
|---|---|---|
| 0 | 1 | |
| 0 | ||
| 0 | ||
| 1 | ||
| 0 | ||
| 1 |
The way we fill in the table is we do the following on each row:
| Old | Digit | New |
|---|---|---|
| 0 | 1 | 1 |
| 2 | 0 | 2 |
| 4 | 0 | 4 |
| 8 | 1 | 9 |
| 18 | 0 | 18 |
| 36 | 1 | 37 |
The decimal result is in the bottow of the ``New'' column.
I actually don't make any claim that this is easier for people to do than just looking at the positions and multiplying by the right powers. But it's a whole lot easier to put in a computer program!
This is called the multiplication method, as we multiply in each step.
Readers of The Hitch Hiker's Guide To The Galaxy have encountered the Answer to Life, the Universe, and Everything: after much computer effort, it was revealed that the answer was 42. It seems they didn't realize the Answer might not make much sense if they didn't have a clear understanding of the Question...
Not many readers remember that, in one of the later books of the series (I think the second), the Question is "how much is 6 times 9?"
There is actually a radix in which this is correct...