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?
Counting in bases other than 10
Another way to look at it is this- let's say you want to count in
base 8. Well, that means you have a total of 8 digits (symbols) to
work with: 0,1,2,3,4,5,6 and 7. The digits 8 and 9 no longer exist in the
system. If you have nine things then that means in base eight you
have 11 things, and you have 24 fingers and toes. How does this work?
Well, think of the '2' in 24 as being in the eights-place, and the '4'
being in the ones-place. That way, 24 means you have 2 eights, and 4
ones, or twenty. If you have 77 things in base eight, that's seven
eights and 7 ones, or sixty-three things. Adding 1 to 77 and you get
100, which is 1 in the sixty-fours place, zero in the eights place,
and zero in the ones place (when doing arithmetic, carry just like you
do in base ten). So, counting in base 8 would look something like
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).
|Decimal||10||0 1 2 3 4 5 6 7 8 9||6,59|
|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:
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
Converting to decimal
As we said before, at some point your elemetary teacher told you that
the number 236 was really 2 in the "hundreds" place, 3 in the "tens"
place, and 6 in the "ones" place. This idea works across all bases.
If instead you were given the number 236 in octal, that is just 2 in
the "sixty-fours" place, 3 in the "eights" place, and 6 in the "ones"
place. In fact, in any given base n, the digit at the far
right of the number is in the "ones" place, the one next to it is in
the ns place, the one next to that is in the
n2s place, and so on. So, the ith digit
starting from the right is in the nith place.
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.
The Snake Algorithm
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
Place a 0 just above the leftmost digit and a down arrow to the right
of these two digits:
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
Summary of Binary->Decimal Snake Algorithm
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 110012. (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.)
Extending the Snake to Other Bases
When we converted from decimal to binary, we decided what to write by
observing whether the number was even or odd. Another way of doing
the same thing is to write the remainder obtained when the number is
divided by 2. If the number is even, the remainder is 0, and if the
number is odd, the remainder is 1. Thus if the number is denoted by
n, we could have used the expression n % 2 to determine what
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.
Summary of Snake Algorithm
We have now seen examples of numbers represented with bases 2, 8, and
16. We could have used any integer greater than 1 as a base, so that
if b were such an integer, we could talk of numbers represented to
base b. In this case, we represent our numbers as sums of powers of b.
The digits are 0, 1, 2, ..., b-1.
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.
Shortcut For Converting Binary to Bases of a power of 2
It is extremely easy to convert between binary and octal and between
binary and hexadecimal. Indeed, it is easy to convert between binary
and any base b = 2i. As an example, consider the binary
number n = 1011100001. To convert n to hexadecimal
(base 16 = 24), write the bits of n in groups of
size 4, starting from the right.
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 10111000012 = 5E116 To convert n to octal (base 8 = 23), 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 2i 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, 24012768 = 10 100 000 001 010 111 110 = 101000000010101111102.
This is a general method that can be used to convert numbers in any base b to base bi.