Think back to when you first started learning the concept of numbers- those early Sesame Street years. At first, you figured out what 1 and 2 meant, and then something clicked and you realized that 3 meant three things, and that 4 meant four things, etc. However, when you got to 9, you were told that the next number was 10. Notice the subtle change here- from 0-9 we have different characters for each number, but suddenly at 10 we use two different characters placed side-by-side to get the next number. Then, to get the next ten numbers we keep the 1 on the left and count from 0-9 again on the right-- 10, 11, 12, 13....18, 19. Later on, you got the full scoop when you were told that for the number 236, the 2 was in the hundreds-place, the 3 was in the tens-place, and the 6 was in the ones-place. So, the number 236 stood for (2x100)+(3x10)+6.
Great- so what does this have to do with *anything*? Well, why did we stop creating symbols at 9? Couldn't we have come up with some new symbol, say @ to stand for ten things? Well, sure. Stopping at 9 is pretty arbitrary, and we could have stopped, and can stop at any number we want. The thing is, the first number without it's own symbol (henceforth called the base) really affects how numbers look. For example, let's say that the number ten is really given by the symbol @...how would we count then?
0, 1, 2, 3, 4, 5, 6, 7, 10, 11, 12, 13, 14, 15, 16, 17, 20, 21, 22, 23, 24, 25, 26, 27, 30, 31, 32, 33, 34.....
Out of all the arbitrary bases that we can count in, there are four different ones that are important to computer science, decimal (base 10) which is what we all use every day, binary (base 2), octal (base 8), and hexadecimal (base 16).
Representation | Base | Digits | Examples |
---|---|---|---|
Decimal | 10 | 0 1 2 3 4 5 6 7 8 9 | 6,59 |
Binary | 2 | 0 1 | 110,111011 |
Octal | 8 | 0 1 2 3 4 5 6 7 | 6,73 |
Hexadecimal | 16 | 0 1 2 3 4 5 6 7 8 9 A B C D E F | 6,3B |
And counting in these bases looks something like this:
10 | 2 | 8 | 16 |
---|---|---|---|
0 | 0 | 0 | 0 |
1 | 1 | 1 | 1 |
2 | 10 | 2 | 2 |
3 | 11 | 3 | 3 |
4 | 100 | 4 | 4 |
5 | 101 | 5 | 5 |
6 | 110 | 6 | 6 |
7 | 111 | 7 | 7 |
8 | 1000 | 10 | 8 |
9 | 1001 | 11 | 9 |
10 | 1010 | 12 | A |
11 | 1011 | 13 | B |
12 | 1100 | 14 | C |
13 | 1101 | 15 | D |
14 | 1110 | 16 | E |
15 | 1111 | 17 | F |
16 | 10000 | 20 | 10 |
17 | 10001 | 21 | 11 |
18 | 10010 | 22 | 12 |
19 | 10011 | 23 | 13 |
When we see the number 1011, for example, we assume it is the decimal number "one thousand eleven". But 1011 is also a perfectly valid binary number. When there is a possibility of confusion, the base of the number is sometimes written as a subscript, as in
1011 == 11 == 13 == B 2 10 8 16
For Example:
An easy was to go about doing this coversion is to follow HORNER's RULE, but sometimes it is called more informally, the snake method.
Convert the binary number 11001 to decimal.
We begin by spreading the digits out as follows:
The snake method utilizes two kinds of moves, veritcal (either up or down), and horizontal. Vertical moves correspond to addition, and horizontal moves correspond to multiplication by the base (in this case 2).
Since the arrow is vertical, we add the two digits to get:
and follow the sum with a right arrow. This tells us to multiply the sum by 2 to get:
and we follow it with an up arrow. We always alternate horizontal and vertical moves, adding on vertical moves and multiplying by 2 on horizontal moves. Thus, the next step gives us:
Snake through the digits in this way until there are no further digits to the right:
The final number, 25, is the decimal representation of 11001_{2}.
For example, if we start with the decimal number 25
we observe that it is odd so we write a 1 above it and subtract.
Divide 24 by 2 and write the number 12 to the left
Since 12 is even, we write a 0 below it and subtract 0 from 12 to get 12
We divide 12 by 2 and write the 6 to the left. Since 6 is even, we write a 0 above it and subtract 0 from 6 to get the 6 we write above the 0. Now divide 6 by 2 and write the 3 to the left. Since 3 is odd, we write a 1 below it and subtract to get 2, which is written below the 1. Divide 2 by 2 to get 1 which is written to the left. Since 1 is odd, we write a 1 above it and subtract to get 0, which is written above the 1.
This terminates the algorithm, and we read the answer 11001_{2}. (Actually, it doesn't matter if we start with a vertical move up or a vertical move down, as long as we stop when we reach zero.)
For example:
Convert the decimal number 234 to octal.
We can use the same type of algorithm as describe above for binary representations to get the octal representations. We again write it at the right end of the page and when we go up or down, we subtract the remainder when the number is divided by 8. When we go to the left, we divide by 8. Here is how it looks:
We read the answer 352 as the octal representation of the number whose decimal representation is 234.
This process can be reversed to get the decimal representation of the number whose octal representation is given, say as 4126. Here is the algorithm:
The decimal representation is thus 2134.
Our algorithm for converting from base b representation to decimal representation is to write the digits of the base b representation spread apart in the middle line. We start with 0 above the leftmost digit. When we move vertically, we add, and when we move horizontally, we multiply by b.
In the other direction, to convert from a decimal representation to a base b representation, we write the decimal representation at the upper right. In the vertical moves, we subtract the remainder of the number when divided by b, and in the horizontal moves, we divide by b.
Now, convert each group into decimal. The numbers are small enough that this can be done by inspection.
Finally, write each digit in hexadecimal.
Therefore 1011100001_{2} = 5E1_{16} To convert n to octal (base 8 = 2^{3}), do the same thing using groups of size 3.
This process is performed so naturally that you will soon be able to convert visual representations of binary data to their hexadecimal equivalent without written effort. The algorithm can be reversed to convert a number in base 2^{i} to binary, by simply writing each digit of n as an i-bit binary number. The only trick is to be careful to use all i bits and write leading zeros when necessary. For example, 2401276_{8} = 10 100 000 001 010 111 110 = 10100000001010111110_{2}.
This is a general method that can be used to convert numbers in any base b to base b^{i}.
Chad Lake