냐컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴� +-+-+-+-+-+-+-+-+ 栢栢栢栢昉께께굇굇굅같�|O|u|t|b|r|e|a|k|臍같굇굇굉께께栢栢栢� +-+-+-+-+-+-+-+-+ Issue #4 - Page 7 of 12 냐컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴컴� Number Systems and Binary Math Written by Meggito on September 1, 2001 Last updated on October 20, 2001 First off, giving credit where credit's due. I'd like to thank Sally = Ballacqua, Mary Johnson, Hanet Mully, and Charles Brewer who's packet = gave me a much better way to look at numbering systems and encouraged a = rewrite of this file. This file starts off with what binary and = hexadecimal are and how to convert to other number systems. Afterward I = use binary math to show how to do math in ANY number system. I use = binary for most math but the multiplication, division, and modulus are = done the same way in other numbering systems. I cover how to and not to = do addition, subtraction, multiplication, division, and modulation. = Also, how to use floating point decimals and multiplication and division = with them. I tried to make it as simple as I could so it is easily = understandable. Decimal The most common number system, the decimal system is based on a system = of ten. Each column can represent ten symbols and each additional = column represents multiples of ten of the column to its right. Meaning = that 9 is nine and 90 is nine multiples of ten. 95 is then nine = multiples of ten followed by 5 multiples of 1. The multiples each column = will represent will depend on the system. In the decimal system it = goes: 0 5, 4 = 6 3. 4 ^ ^ ^ = ^ ^ ^ 10,000 1,000 100 = 10 1 .1 This number would be 5,463.4 when combined, five-thousand, four-hundred, = sixty-three. A good way to look at this is combining each column. The = 'and' is used to represent the decimal point. The number farthest right = without passing a decimal point (.) is always the ones place. If there = is no decimal point then the one place is considered to be the farthest = right. Each group of whole number group of 3 is seperated by a comma. = If there are 0s on either end they may be eliminated except in certain = situations (used to represent a certainty) that unless you're a = scientist aren't important. Many of these rules will follow into other = numbering systems. Binary Binary is also similar to Decimal. The largest difference is that it is = based on either true or false, on or off, or 1 or 0. Each coumn can = only represent one of two numbers. This means that each coumn has a = value of 1 or 0. 1 0 1 1 1 = 0 1 1 0 1 ^ ^ ^ ^ ^ = ^ ^ ^ ^ ^ 256 128 64 32 16 = 8 4 2 1 .5 The above number 101110110.1 would be equivalent to 374.5 (decimal = points or binary points or whatever are rare in binary but do exist). = This is much different from what most people are used to, but if you = wanted to convert it into your familiar decimal system you could = multiply each number by its decimal equivalent. Either you add the = number or you don't, 1 or 0. You can just take the truths and add them. = So 256 + 64 + 32 + 16 + 4 + 2 + .5 =3D 374.5. This causes numbers to = be much longer than in other number systems. This is the system used to = program computers because of the fact that are either true or false. = Programming languages are just representations of these 1s and 0s. Each = of these columns is known as a bit. They are usually grouped into = groups of eight, known as bytes. One byte can represent up to = two-hundred fifty-six possibilities. Usually when you have a number = that uses less than a whole byte, such as 1011 (thirteen) you'd add = valuless 0s to then end to complete the byte, 00001011. This enables = computers to know when one byte ends and another begins. So = 0110110101100101 is the same thing as 01101101 and 01100101 because a = computer will seperate them into groups of eight. This allows an = endless stream of 1s and 0s without any need for spacing, which a = computer cannot recognize, except as another set of 1s and 0s that = aren't seperated. Another odd piece of binary is negatives. There is usually no negative = sign, and never with programming. There are signed and unsigned binary = numbers. If it is signed then the first number represents positive and = negative. 0 is positive and 1 is negative. This also means that an = unsigned 8 bit binary byte can have a value of from 0 to 255 while a = signed binary byte can have a value from -128 to 127. Both do have 256 = possible values though. I'll cover negatives under adding and adding = negatives. Hexadecimal System This system is similar to the decimal system. The difference is that = each column represents sixteen rather than ten. Appropriotly each = column will also refer to sixteen multiples of the column to its right. = Since the arabic writting system only has ten number characters the = numbers eleven throguh sixteen are represented by the letters A thourgh = F. Meaning that thirteen would be D and fifteen F. Remember, A is 10, = not 11. I still make that mistake occasionally. 5 A 3 = 8 B 5 ^ ^ ^ = ^ ^ ^=20 65536 4096 256 = 16 1 .0625 This would then be 5a38b.5. Meaning 5 x 65536, 11 x 4096, 3 x 256, etc. = You can follow a similar approach to convert this as you did with = binary. You would then find that this number is equivalent to = 369,547.0625 in the decimal system. Hexadecimal, or hex, is often used = in programming. Since group is equivalent to 1000 in binary, = hexadecimal is very useful to computer programming. One example of this = is the very common use of hex code to represent colors. They use two = columns to represent each of the three colors used in computers, red, = green and blue. They are usually set up in the format RRGGBB where each = letter represents the color relatively. Using the hex code any value = between 0 and 256 (one byte) can be used to represent the amount of each = color present. So you might find 5E425A used to represent a color. = This would mean that there was 94 red, 66 green, and 90 blue out of a = possible 256 each (a fairly grayish purple). This ability to converge = on the same numbers as binary makes it very useful on computers. Other Ways to Convert One other method to look at ocnverting numbers is multiplying each digit = by the base raised to the power of the digits location relative to the = one's place. If yo don't allready know any number to the 1st power is = itself and to the 0 power it is always 1. Note that all powers and = roots are based on base 10. Base 10 Base 7 342 =3D 3*(10^2) + 4*(10^1) + 2*(10^0) 4526 =3D 4*(7^3) + 5*(7^2) = + 2*(7^1) + 6*(7^0) =3D 3*100 + 4*10 + 2*1 =3D = 4*343 + 5*49 + 2*7 + 6*1 =3D 300+40+2 = =3D 1372+245+14+6 =3D 342 = =3D 1637 To reverse this you divide by the base you want to change to and keep = track of the remainders. Keep dividing until you get 0. The examples = start from the bottom and work up! Read the awnser top down. You can = do it the other way if you like but its a lot easier if you find youself = having to do it on paper just to write the awnser above as you divide. 224 Base 10 to Base 2 519 Base 10 to Base 13 1/2 =3D 0 R 1 3/2 =3D 1 R 1 7/2 =3D 3 R 1 14/2 =3D 7 R 0 28/2 =3D 14 R 0 56/2 =3D 28 R 0 3/13 =3D 0 R3 112/2 =3D 56 R 0 39/13 =3D 3 R0 224/2 =3D 112 R 0 =3D11100000 519/13 =3D 39 RC =3D30C Binary to Hexadecimal and Back The fact that binary is base 2 and hexadecimal is base 2 to the 4th = makes conversion simple. You just take each group of four binary digits = and convert them one group at a time. The reverse is also true, look at = the examples. 011001011110 can be split into groups of four... 0110-0101-1110 then you find the hexadecimal value for each group so... 6 5 E or 65E so 011001011110 =3D 65E A3F can be reverse by splitting each into its binary value so A 3 F =3D 1010-0011-1111 This method can be used whenever the base of one system is divisible by = another. It is based on logarithms that I'm not going into but its = fairly simple math. If you had a base 3 and a base 9 then 3 base a bas = 9 digit would be 2 base 3 digits and 2 base 3 digits could convert to = base 9. Binary Addition and Adding Negative Numbers Adding and subtracting unsigned binary numbers is fairly simple. You = must remember to carry numbers over. Also when programming with a = limited numbering of bits any numbers carried over will be lost. These = examples are all 8 bit. 121 01111001 +183 10110111 304 100110000 but the leading 1 is lost so 00110000 or 48 In this example an two unsigned 8-bit numbers were added. There total = was 304 but since any numbers carried past the number of bits allowed = are lost. This means that after 255 the next number is 0. Subtracting = is similar but slightly instead of subtracting you add the negative. To = find the negative you take what is called the two's complement. First = you find the complement of each bit (if you don't understand = complements, change a 0 to a 1 and a 1 to a 0) to find the one's = complement. Next you add 1 to that number to find the two's complement. = This is the negative of the original number (also how you find = negative's) and you just add that instead of subtracting. 58 42 =3D 00101010 so... = 58 00111010 -42 one's complement =3D 11010101 +(-42) 11010110 16 two's complement =3D 11010110 16 = 00010000 If the answer is negative or you just want to change a negative number = to positive reverse this. First you subtract 1, (add 11111111), then = finding the complement of each bit again. 11010110 11010101 +11111111 00101010 so... 11010101 42 It is important to remember that if the number is unsigned that there = isn't a negative. Multiplication and Long Division Multiplication is fairly simple. If you had 3*7 you'd just do 7+7+7. = This is how a computer does multiplication. 1221 (carry over) Simpler 3 00000011 so 00000111 00000111 /-> 00001110 *7 00000111 00000111 00000111 / 00000111 21 00010101 00000111 00001110 --/ 00010101 =3D 21 00010101 =3D 21 The only problem here is that this doesn't work real well for larger = numbers. No, well have to use long multiplication (well, they call it = long division) because we aren't computers who can perform millions or = additions a second. 13 00001101 1101 *5 00000101 *101 65 01000001 1101 00 +110100 1000001 =3D 65 Dividing is slightly different. Instead of adding you could multiple by = the reciprical. This means instead of multiplying by 7 you multiply by = 1/7. Also, remember that any number /1 equals itself. 14 00001110 00001110 * 00000001 =3D 00001110 =3D 14 7 00000111 00000001 * 00000111 =3D 00000111 =3D 7 2 00000010 So, if you have any smarts about you you'll notice that the awnser is 14 = over 7 which takes us back to where we started. Kinda useless isn't it. = Just a good thing to know doesn't work. This is where long division = comes in... 14 00001110 0010 or 0010 =3D 2 7 00000111 111/1110 2 00000010 This is kinda simple because I used easy numbers. When you get to = 0000111, 000001111 will go into it once (you can ignore the leading 0s). = It gets much more complicated but it can be done. Since these are = simple numbers it is unnecessary to turn them into negatives but you may = have to in many cases. 15 00001111 0001.111 =3D 1+.5+.25+.125 8 00001000 1000/1111 1.875 1.875 00000001.111 -1000 01110 -1000 01100 -1000 01000 -1000 0000 Problem is that unless you're using a data type that recognizes decimals = (int doesn't unless you put them deliberately put them in) the decimals = will be lost. If these were both ints the answer would be 1. This is = when modulus comes in. Most people have not run into modulus before = programming. Modulus is basically the remainder when after being = divided. The symbol for modulus is %. For example, 15%8 would be the = remainder when dividing by 8, so the answer is 7. When doing this in = binary just stop when you run out of numbers, no decimal point (or = whatever), and take whatever's left. You may need to change these = numbers to negatives if you do not understand the subtration. 17 00010001 00000101 =3D 7 (division) %3 00000011 11/00010001 2 00000010 -11 0100 -11 010 =3D 2 (modulus) Modulus comes at the same time as multiplication and division in the = orders of operation. You read it from left to right and do whichever = comes first of the 3. In both multiplication and division of 2s or multiples of 2s all you = have to do is shift numbers. Multiplication shifts left and division = shifts right. For example, 0110*2=3D1100 and 0110/2=3D0011. Also, = 00110000*4=3D11000000 and 00110000/8=3D00000110. You shift it but the = exponent 2 is to. Since 8 is 2^3 you move it 3 digits. The same is = true of modulus, all you have to do is shift it right as you would in = division and then take the value after the decimal. So 0101%2=3D010.1 = or 1. 0111%8=3D.111 or 7. Floating=20 A while ago the IEEE (Institute of Electrical Engineers) came up with a = standard 32 bit representation for floating points. There are 3 parts = to this, the sign is 1 bit, the exponent is 8, and the mantissa is 23. 01101100111010000000000000000000 | |______||___________________| | | | | Exponent Mantissa Sign The sign decides whether a number is positive or negative in the same = way as a signed bit. The exponent is the power that the mantissa is to. = The mantissa is the value to the exponent. To find a number's mantissa = and exponent divide it by 2 until it is between 0 and 1. The mantissa = is the remainder ignore the decimal point. The exponent is the number = of times you had to divide added to 127. An easy way to find the = exponent without converting to decimal is to just add a 1 in the first = digit and subtract 1 from the number. So 7 is 10000110. 13/2 =3D 6.5/2 =3D 3.25/2 =3D 1.625/2 =3D 0.8125 So the mantissa is 0.8125 and the exponent is 131 (4+127) Which in binary the mantissa is 0.1101 (notice that 1101 is 13) and the = exponent is 10000011 This would be rewritten as 0-10000011-11010000000000000000000 So 13 =3D 00001101 =3D 010000011110100000000000000000000000 This can also be done starting with a binary number. There is a big = advantage in that since you are dividing by 2 you can just shift it left = until there is no 1 (value) after the decimal and the number of times = you've shifted is the exponent. When using negatives carry the 1 over = to the mantissa and do not worry about finding the two's compliment. 00000110 So the exponent is 10000010 because you've shifted 3 The mantissa is 110 (the number after the first 1) + twenty 0s to make = it 23 digits This means your final number is 01000001011000000000000000000000 So 00000110 =3D 01000001011000000000000000000000 Multiplication and Division, Floating Point Style All you have to do with mantissas to multiply or divide is add or = subtract the sign and exponents and multiply or divid the mantissas = respectively. Obviously adding is multiplication and subtracting is = division. Do not use the first digit in the exponent when adding, it = will always be a 1. When using negative's it is not necessary and = usually easier not to find the two's compliment. Multiplication 11 =3D 00001011 =3D 0 10000011 10110000000000000000000 5 =3D 00000101 =3D 0 10000010 10100000000000000000000 55 =3D 00110111 =3D 0 10000101 11011100000000000000000 = (1011*101=3D110111) Division 30 =3D 00011110 =3D 0 10000100 11110000000000000000000 -6 =3D 00000110 =3D 1 10000010 11000000000000000000000 -5 =3D 00000101 =3D 1 10000010 10100000000000000000000 (1111/11=3D101) I beleive I am mistaken slightly on this. I think there is something = you're supposed to do with the leading 1 in the exponent but I do not = know what. Also You may have to convert into two's compliment for = negative numbers. I'd be surprised if the two weren't related. Either = way just carrying the negative to the sign works fine. ASCII and Symbols ASCII, or American Standard Code for Information Interchange, was = proposed by ANSI as a way to represent symbols (letters, numbers, etc.) = with a byte. They developed a set of one-hundred twenty eight basic = symbols that most computers represent. Each corresponds to a certain = number as listed in a second. This set of 128 symbols is fairly = standard though it varies some. Other symbols are available in the = other possible 128 symbols, the extended set. One problem is that there = are a variety of extended sets, many using different symbols and = arrangements. There are also other standards such as Unicode(16 bit = multi-writing-system, ie Traditional Chinese) and EBCDIC (Extended = Binary Coded Decimal Interchange Code) that are much less common. For = those of you who don't know this, hold alt and hit one of these key = combinations. Pretty useless except for the extended set but good to = know. I'm leaving out the first 32 symbols and 127 because they are to be = recognized by your computer. I can't think of any reason other than = programming to ever know them, and if you're programming then you have = them or can get them. 000 - - 00000000 064 - @ - 01000000 001 - - 00000001 065 - A - 01000001 002 - - 00000010 066 - B - 01000010 003 - - 00000011 067 - C - 01000011 004 - - 00000100 068 - D - 01000100 005 - - 00000101 069 - E - 01000101 006 - - 00000110 070 - F - 01000110 007 - - 00000111 071 - G - 01000111 008 - - 00001000 072 - H - 01001000 009 - - 00001001 073 - I - 01001001 010 - - 00001010 074 - J - 01001010 011 - - 00001011 075 - K - 01001011 012 - - 00001100 076 - L - 01001100 013 - - 00001101 077 - M - 01001101 014 - - 00001110 078 - N - 01001110 015 - - 00001111 079 - O - 01001111 016 - - 00010000 080 - P - 01010000 017 - - 00010001 081 - Q - 01010001 018 - - 00010010 082 - R - 01010010 019 - - 00010011 083 - S - 01010011 020 - - 00010100 084 - T - 01010100 021 - - 00010101 085 - U - 01010101 022 - - 00010110 086 - V - 01010110 023 - - 00010111 087 - W - 01010111 024 - - 00011000 088 - X - 01011000 025 - - 00011001 089 - Y - 01011001 026 - - 00011010 090 - Z - 01011010 027 - - 00011011 091 - [ - 01011011 028 - - 00011100 092 - \ - 01011100 029 - - 00011101 093 - ] - 01011101 030 - - 00011110 094 - ^ - 01011110 031 - - 00011111 095 - _ - 01011111 032 - (space) - 00100000 096 - ` - 01100000 033 - ! - 00100001 097 - a - 01100001 034 - " - 00100010 098 - b - 01100010 035 - # - 00100011 099 - c - 01100011 036 - $ - 00100100 100 - d - 01100100 037 - % - 00100101 101 - e - 01100101 038 - & - 00100110 102 - f - 01100110 039 - ' - 00100111 103 - g - 01100111 040 - ( - 00101000 104 - h - 01101000 041 - ) - 00101001 105 - i - 01101001 042 - * - 00101010 106 - j - 01101010 043 - + - 00101011 107 - k - 01101011 044 - , - 00101100 108 - l - 01101100 045 - - - 00101101 109 - m - 01101101 046 - . - 00101110 110 - n - 01101110 047 - / - 00101111 111 - o - 01101111 048 - 0 - 00110000 112 - p - 01110000 049 - 1 - 00110001 113 - q - 01110001 050 - 2 - 00110010 114 - r - 01110010 051 - 3 - 00110011 115 - s - 01110011 052 - 4 - 00110100 116 - t - 01110100 053 - 5 - 00110101 117 - u - 01110101 054 - 6 - 00110110 118 - v - 01110110 055 - 7 - 00110111 119 - w - 01110111 056 - 8 - 00111000 120 - x - 01111000 057 - 9 - 00111001 121 - y - 01111001 058 - : - 00111010 122 - z - 01111010 059 - ; - 00111011 123 - { - 01111011 060 - < - 00111100 124 - | - 01111100 061 - =3D - 00111101 125 - } - 01111101 062 - > - 00111110 126 - ~ - 01011110 063 - ? - 00111111 127 - - 01011111