Number Systems and Number Conversions by James Tam Introduction: The number system that we all learnt from grade school onwards is of course base 10 (decimal). However because computers do not work in base 10 but in base 2 (binary) we as computer scientists must learn this second number system. Since trying to debug your program by looking at line after line of base two numbers is a real pain, base 8 representations (octal) were first used. Later when computers became faster (when 16 bit machines were developed) base 16 (hexidecimal) representations became more common. Fortunately with the development of high level languages (ones closer to regular English) there was a declining need to debug programs by looking at the octal equivilent of your program let alone write code this way. The control character '^\' stops your program and creates a core file that can be used to debug your code. The core file contains information on the state of the machine as the program executes (values in memory, registers etc.) For those of you who are keen, curious or just have too much free time pull up the man pages on the command 'od' - octal dump on the core file so that you can view it (just remember NOT to print the octal dump out via lpr). Back in the olden days of computing, when I was in CPSC 213 (it was 211 and 213 rather than 231 & 233 the way it is now) we would produce a core file for programs that we wrote, run it through 'od' to convert the binary values to octal and not so merrily debug our programs that way. So I can tell you from first hand experience that working on assignments while staring at column after column of octal wasn't a great joy. But as a hold-over from these bygone days the use of non-decimal based number systems is still taught in almost all firstyear Computer Science courses. For study purposes you might want to take the table below and memorize it for the number conversion questions on exams. I find that doing conversion from say decimal to binary can be tricky enough without doing all the calculations in your head. Table of Numbers in 4 different bases: Decimal(10) Binary(2) Octal(8) Hexidecimal(16) 0 0000 0 0 1 0001 1 1 2 0010 2 2 3 0011 3 3 4 0100 4 4 5 0101 5 5 6 0110 6 6 7 0111 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 Notice that the largest equivilent single digit decimal number that you can represent in any given base is equal to the base minus one. So in the case of base ten, the largest single decimal number that we can represent is 9 (10 - 1). The largest single digit decimal number we can represent when we use all the alpha-numeric characters is 35. (We have 10 numbers plus 26 alphabetic letters to yeild 36 possibilities for a base 36 system. The maximum decimal number that we can represent using a single base 36 digit is 35 because of course 36 - 1 is equal to 35). Conversions between bases: As a tip, when converting between decimal and octal or hex, always try to do the conversions first to binary then to either octal or hex. Makes life much easier and helps one sleep well at night. Binary to Octal / Octal to Binary: Group the bits in groups of three, since octal is base eight and 2 raised to the power of 3 is equal to eight. Use these three bits to find the octal value: Binary Octal 000 0 001 1 010 2 011 3 100 4 101 5 110 6 111 7 You should also notice that converting from octal to Binary is merely reversing the process. For every octal digit you get three binary ones. Finally note that when you have a fractional binary value, you group the bits of the integer portion starting on the right hand side of the decimal point. You group the bits for the fractional portion starting on the left hand side of the decimal point. eg.-11111.1111 in binary. is grouped like this: 11 111.111 1 or 37.71 in octal. Binary to Hex/ Hex to Binary: Group bits in groups of four since 2 raised to the 4th power is equal to 16. Here's the chart from above but showing only the binary and hex values: Binary(2) Hexidecimal(16) 0000 0 0001 1 0010 2 0011 3 0100 4 0101 5 0110 6 0111 7 1000 8 1001 9 1010 A 1011 B 1100 C 1101 D 1110 E 1111 F And again the reverse applies when converting from hex to binary. For every hex digit you will get 4 binary ones. Grouping the binary digits works in the same way as with octal. When you have a fractional binary number start grouping the integer portion on the staring left hand side of the decimal point and group the fractional poriton starting on the right hand side of the decimal point. eg.-11111.11111111 in binary is grouped like this: 1 1111.1111 1111 1F.FF in hex. Converting from any base to decimal: Note that the "^" symbol stands for an exponent. Similar to binary to octal and hex conversion you must group your digits starting at the decimal point as follows: Superscript 3 2 1 0 -1 -2 Digit x x x x. x x eg.- 12.5 in octal In decimal = 1*(8^1) + 2*(8^0) + 5*(8^-1) = 8 + 2 + 5/8 = 10 5/8 = 10.625 Converting from decimal to any base: First split the number up to the integer and decimal portions. For the integer portion take the number and divide it by the target base. The remainder becomes the first digit to the left of the decimal. Then take this quotient and divide it by the target base. This new remainder becomes the second digit left of the decimal. Continue dividing through until the quotient becomes smaller than the target base. This final quotient becomes the digit furthest on the left from the decimal. e.g. - Converting 9 in base ten to a value in base two, divide the number to be converted by the target base (in this case two). The remainder of the division becomes the resulting binary number starting on the right hand side of the decimal place and working our ways leftwards. The quotient is now divided by the target base. Continue until the remainder of the division is less than the target base (in this case stop when the remainder is less than two). Binary value: 1 0 0 1. ^ ^ ^ ^ ---------4 | | | | | _ | | | | | 2|9 | | | | | 8 | | | | | - | | | | Become | r = 1------------------------------------ new | | | | the | | | | value | ------ 2 | | | | | _ | | | ------>2|4 | | | | 4 | | | | _ | | | | | | | | r = 0--------------------------------- | | | | | | --------- 1 | | | | _ | | | --->2|2 | | | 2 | | | _ | | | r = 0------------------------------ | | | | | 0 | | _ | ------->2|1 | r = 1-------------------------- For the fractional portion you perform sucessive multiplies using the target base. The integer part after the multiply becomes the first digit to the left of the decimal. If the integer part is less then 1 after the multiplication then the number is zero. Take remaining decimal portion and multiply it again by the target base. The integer portion again becomes the digit second from the right of the decimal. Continue until either the decimal portion finally becomes zero or you have enough places of precision. e.g. - Convert 0.5 in base ten to a value in base eight. Resulting octal value: 0.4 Number to convert-> 0.5 ^ Target base-> * 8 | ---- | 4.0 | | | -----------------------------| Fractional part The whole number part of | of product the multiply becomes the | becomes the input converted digit | to the multiply | function. | \ / 0.0 * 8 --- 0.0 Note: we stop multiplying in this case because further calculations would be rather useless - all we would be is more zeros. If we don't face the case of repeating zeros then we would continue the multiplication until we reach the desired number of decimal places of precision. Addition in non decimal bases: Basically it's done in the same way that you do in decimal. Just keep in mind the following table 0 0 1 1 +0 +1 +0 +1 -- -- -- -- 0 1 1 10 (this is a zero in this column and a carry over of 1 to the next column). And of course the case when we are adding 1 + 1 and we have carry over of 1 from a previous column 1 +1 +1 -- 11 (we get a 1 in this column and carry over of 1 to the ext column) eg.- 1000 plus 0010 both binary numbers. Binary Decimal 1000 8 +0010 +2 ----- -- 1010 10 Multiplication in non decimal bases: Again it's very close to what you are used to in decimal: eg.-100 times 010 in binary. Binary Decimal 100 4 x010 x2 ---- -- 000 8 100 000 ----- 01000 = 8 Subtraction in non decimal bases: The only thing that makes it different from decimal based subtraction is when you need to do a borrow. When you do a borrow from one column to another in base ten you borrow ten which is equal to the base. When you need to do a borrow in a non base ten number system then the amount that you do the borrow by is equal to the base. eg.- Octal Decimal 400 256 -370 -248 ---- ---- 010 8 In the second column when we have 0 - 7 we need to do a borrow from the previous column. We do the borrow and the 4 becomes a 3. The value that we borrow equals the base = 8 and we do the remaining subtractions in column 2 as we would in decimal (8 + 0 - 7 = 1).