Different Ways to Represent Numbers

Contents:

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..8..9..@..10..11..12..13..14..15..16..17..18..19..1@..20..21..22..23..24...
Pretty weird, huh? This is counting in base eleven, because the first number without its own symbol (10) is the eleventh number. What is really weird is that is that you no longer have 10 fingers...you have @ fingers, because since we now have ten different symbols to use, once we switch to 10, that is 1 in the elevens place, and 0 in the ones place. So, really there are 11 inches in a foot. There are still just 4 Beatles (John, Paul, Ringo, George), but there are 46 states in the United States of America (that's 4 in the elevens place plus 6 in the ones place, or fourty-four plus six which is fifty). Counting in this way can be really weird until you get used to it (note: there was actually a song written about this once, if you can believe it, and you can listen to it, if you have an mp3 player).

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 this:
```   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).

RepresentationBaseDigitsExamples
Decimal100 1 2 3 4 5 6 7 8 96,59
Binary20 1110,111011
Octal8 0 1 2 3 4 5 6 76,73
Hexadecimal160 1 2 3 4 5 6 7 8 9 A B C D E F6,3B

And counting in these bases looks something like this:

102816
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
1610000 20 10
1710001 21 11
1810010 22 12
1910011 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
```

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.

For Example:

Octal->Decimal
428 = (4 * 8) + (2 * 1) = 3410
Binary->Decimal
110012 = (1 * 24) + (1 * 23) + (0 * 22) + (0 * 21) + (1 * 20) = 1610 + 810 + 110 = 2510

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

For example:

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).

The Algorithm

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 110012.

Summary of Binary->Decimal Snake Algorithm

Step 1:
Write the binary number, with the bits spread out, and so there is enough space above and below each bit to write an intermediate result.
Step 2:
Write a 0 in the space above the most significant (leftmost) bit.
Step 3:
Repeatedly do one of the following operations until all of the spaces above and below the bits are filled:
1. If the last intermediate result was written above (below) the bit at position p and there is an empty space below (above) that bit, then write the sum of the last intermediate result and the bit at position p in the space below (above) that bit.
2. If case (1) does not apply, then write the product of the last intermediate result and 2 in the space immediately to the right of the last intermediate result.
Finally:
The final space filled contains the decimal representation of the number given in binary notation.

Decimal->Binary Snake

We can reverse the snake algorithm to convert a number from its decimal representation to its binary representation. Going up or down corresponds to subtraction and going left corresponds to division.

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 to write.

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.

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.