TAMU Computer Science People Pages



Numbering Systems and Binary MathThe overall conceptCS majors must understand the basic numbering systems and WHY (explained later) they are used. The basic numbering systems areBinary (base 2)Decimal (base 10)Octal (base 8)Hexadecimal (base 16)Base means how many character options you havebinary, you have only two options ( base 2 = 0 – 1)options usually START at 0none of the character used in representing the numbers are negativewhich is an issue, we have to devise a plan for thisIf you have an understanding of the number systems, you will need to use and understand them for the following topics in computer sciencehow to calculate network addresses how to read memory address locations in core dumps understand the color definitions in web and application programming understand many other conceptsDecimalmost commonwhat we use everydayis a base 10 system meaning that each digit is powered by an increasing value with the base digit of 10possible digit values (10)0 - 9Decimal Examplebut why is it used?what we were taught no matter the cultureused in many NON-MATH applicationsphonesaddressesetc…Binaryused in many computer science applicationselectronics (0 = off, 1 = on)decisions (0 = false, 1 = true)is a base 2 system meaning that each digit is powered by an increasing value with the base digit of 2possible digit values (2)0 - 1Binary ExampleOrder and Representation of Decimal values in Bits1286432168421Decimal00000000=000000001=100000010=200000011=300000100=4…=…#1286432168421Decimal00000000=000000001=100000010=200000011=300000100=4ex.01110000=101001011=211111000=301110101=410110010=510110001=610000000=701001001=800010110=901011001=1010001100=1100000111=1210110100=1310001111=1401010111=1500101011=1600011011=1700001000=#1286432168421DecimalEx.=1171=862=1583=2014=1365=2506=1797=238=1009=20010=231Another way of converting a Decimal to Binary24897111958368 ÷ 2 = 34 R 034 ÷ 2 = 17 R 017 ÷ 2 = 8 R 1 8 ÷ 2 = 4 R 0 4 ÷ 2 = 2 R 0 2 ÷ 2 = 1 R 0 1 ÷ 2 = 0 R 11 0 0 0 1 0 0 = 68 (base 10)…0068 ÷ 2 = 34 R 034 ÷ 2 = 17 R 017 ÷ 2 = 8 R 1 8 ÷ 2 = 4 R 0 4 ÷ 2 = 2 R 0 2 ÷ 2 = 1 R 0 1 ÷ 2 = 0 R 11 0 0 0 1 0 0 = 68 (base 10)…But why is it used?simplest to determine electricallyyes/noon/offcombine these and it gets more powerfulused in writing data to a hard drivethe On/off’s are converted back to data (and vise versa when we save data)there has to be SOME type of conversion from the 1/0s to data to make senseHow 0s and 1s are so importantHow 0/1 are storedHow they have a pattern (Play Binary Bingo here!!)Hexadecimalused in many computer science applicationsmemory valuescolor values (HTML)is a base 16 system meaning there are 16 possible digit valuesuses a letter (A-F) to keep it a SINGLE characterHexadecimal ValuesDecimalHex0011223344556677889910A11B12C13D14E15FHexadecimal Example160=1161=16162=256163=4096164=65536But why is it used?since HEX can range MANY more values than binary or decimalused for determining color on a webpagewe can see (and a monitor can display) 16+ million colors!!from black to white and all shades and colors in between!!How is Hexadecimal used?What code is white?What code is black?Converting Decimal to HexadecimalExpress the decimal numbers of the exercises below in hexadecimal notation.1.1684?2.742?3.111Express the hexadecimal numbers of the exercises below in decimal notation.1.E2?2.987?3.FFF4.A4?5.CDD3?6.4E87.AA538.12BB9.1AFFOctalused in many (some outdated) computer science applicationsmemory valuescircuit boards/roboticsis a base 8 system meaning there are 8 possible digit valuespossible digit values (0-7)Hexadecimal ValuesDecimalOctal0011223344556677810911Octal Example80=181=882=6483=51284=4096But why is it used?not many examples anymoreold 8 bit systems (only had 8 inputs)Octal is used as shorthand for representing file permissions on UNIX systems. Octal in an Application-rw-r--r-- = 0 [1,1,0][1,0,0][1,0,0] = 0 6 4 4 octal to decimal conversionExpress the decimal numbers of the exercises below in octal notation.1.1684?2.742?3.111Express the octal numbers of the exercises below in decimal notation.1.72?2.175?3.1277Binary Mathematics - AdditionSolved much like normal numbersFour rules to remember when solving:0 + 0 = 01 + 0 = 11 + 1 = 0, plus 1 carry (carry over to the next number)Carry + 1 + 1 = 1, plus 1 carryvalue can spill to NEW digit!!! (Example 2)Binary Addition ExamplesExample 1Example 2101101110+ 1011010111001000 10111110+ 1011110100011100Try these problems 1010+1111 111+110 101+111 111+111 1010+1010 11101+ 1010 11111 +11111 1001+1000Ans1100111011100111010100100111111110Binary Mathematics - SubtractionSolved much like normal numberswhen borrowing, it is considered 1010(binary 10, not 10 decimal) – 1 = 1How to Reduce in SubtractionBinary Subtraction ExamplesExample 1Example 2 10110- 01101 1001 1100110- 1011001 1101Try these problems110 - 10 101 - 111001 - 11 1101 - 1110001 - 100 111- 110 111- 111 1011011110- 1011011110Answers:10010110101011010010Issues with Binary Subtractionissues arise when the RESULT is > 0in solving, we need to reduce, but there isn’t anything left!!this issue will be solved using Two’s ComplimentIssues in Subtracting with a Negative resultScenario 1Scenario 2Binary Mathematics – MultiplicationSolved much like normal numbers0 * 0 = 00 * 1 = 01 * 0 = 01 * 1 = 1much like AND Gate!!!Binary Multiplication ExamplesExample 1Example 2 1100100 x 01011 1100100 11001000 000000000 11001000000000000000001101001100 10110111 x 111111 10110111 101101110 1011011100 10110111000 101101110000 101101110000010110100001001Try these problems 10 x 10 100 x 11 101 x 101011 x 1111011 x 101 Answers:1001100101010000110000111Binary Mathematics – DivisionSolving using long division!!!Remember to use BINARY subtraction!!!there are remainders!! (Examples, R 1, R 10, etc…)Binary Division ExamplesExample 1Example 2 10101.1 10110 _________ __________10 | 101011.0 101 | 1101110 -10 101 010 111 -10 101 011 101 -10 101 10 00 10 0Ex. #1 = 10101 R 1Try these problems#1. 100 / 10#2. 111 / 11#3. 1010 / 100#4. 1101 / 11#5. 10111 / 10#6. 11111/100wers:1010 R 110 R 10100 R 11011 R 1Negative Numbers and Two’s Complimentremember how we couldn’t subtract in binary math is the result was negative?in dealing with this, we have to concern ourselves with a few thingswith the number of bits we are allowed (SIZE)the layout of the overall storage of the bitsLSB = Least Significant Bit (always the rightmost bit)MSB = Most Significant Bit (always the leftmost bit)MSB/LSBwe use two’s Compliment to show negative numbersMSB is always negative and the most (absolute) valuespecific algorithm trigger MSB to 1 if the value is negativeadd others (those with 1) to negative MSB valueAlgorithm to create negative numbersWhat would be the MAXIMUM positive value in a 4 bit system?What would be the MINIMUM negative value in a 4 bit system? Answerb:Creating -3 in Twos Compliment (3 and 4 bit)Two’s compliment algorithm version 2!!invert all bitsadd onethen subtractComplete the tables below for Two’s ComplimentValue (base 10)3210000-1-2-3-4Value 765432100000-1-2-3-4-5-6-7-8Adding(and -) numbers in Two’s Complimentsame as we have before butMSB still has meaning0 = positive number1 = negative numbersize again matters, and carry is IGNOREDIn subtracting, here’s the trick, we’re going to ADD the negative numbers togetherin two’s compliment, it still works outAdding Two’s Compliment ExampleConvert these to Two’s Complement then solve, all are in 4 bit systems: 5+ - 3 6 + - 1 4 + - 6 2 + -4 1+ - 5FYI – SectionRepresenting Rational Numbers (Fixed)This will explain why the datatype FLOAT/DOUBLE is so much larger than an INTEGERthe overall game planwe cannot store a LITERAL dot in a floating point numberwe have to address where the “dot” (called a radix)convert the fractional portionconvert the decimal portion (easy)fit it all in a ??? bit system!!Python Data typeDescription and examplesintegersigned integer, 32 bits,?2147483647float64 bit double precision, like 1.23 or 7.8e-28careful, breakdown of the byte (8 bits) can be differentthe “.” is called a RADIXthe radix allows us to use the 4 bits as optimally as possibleradix “moves” left if more space for the decimal portion is neededradix “moves” right if more space for the integer portion is neededuses Exponent portionthis is in EXCESS notation!! (backwards of sign!!)tells us where to move the “radix”+ value in excess means move right- value in excess means move leftBreakdown of the fractional bytethe sign portions MSB0 = + 1 = -Mantissasame as regular binarywhich will have the whole and fractional valueReview of Fractionsfractionaldecimalhalves??/2.50fourths??/4.25eighths??/8.125sixteenths??/16.0625thrityseconds??/32.03125Order and Representation of Fractional values in BitsExpradix.50.25.125.0625.03125…Decimal.00000-=0.10000-=.50.01000-=.25.00100-=.125.00010-=.0625.00001-=.03125.11000-=.75.11100-=.875.11110-=.9375.11111-=.96875…=…Representing Rational Numbers (Floating) from Float to Binarythe overall algorithm from Float to BinaryDetermine the sign bitConvert the integer portion to binaryConvert the fractional portion to binaryMove the radix to the left of the most significant digit (left-most non-zero digit)Determine the exponent in excess 3 notationConverting +2 3/4 (2.75) to binaryThis is positive so our sign bit is 0 2 is 10 3/4 is .11 This gives us 10.11Move the radix two places to the left: .1011 So the exponent is +2: 110 in excess Giving us: 0 110 1011 Converting +0 3/4 (0.75) to binaryThis is positive so our sign bit is 0 0 is 00 3/4 is .11 This gives us 00.11Move the radix two places to the right: 0011. So the exponent is -2: 010 in excess Giving us: 0 010 1011 Solve:-1.1875+0.3437510111100 in decimal01011010Answersb:Negative Numbers and Excess NotationSimpleMSB is key if +/-1 = positive0 = negativeSWITCHED!!!loose one bit to sign, rest are used normallyExcess Notation ChartRepresentationValue000-4001-3010-2011-11000101111021113Answer SectionRange of two’s compliment in a 4 bit systemFloating to Binary (and Vise Versa)? -1.1875 This is negative so our sign bit is 1 1 is 1 .1875 is 3/16 giving us .0011 This gives us 1.0011: Because we have 4 bits we have to use 1.001: Move the radix one place to the left: .1001 So the exponent is +1: 101 in excess 3 Giving us: 1 101 1001 ? +0.34375 This is positive so our sign bit is 0 There is no whole number part .34375 is 11/32 giving us .01011: We need four significant digits. The leading zero is not significant. This gives us 0.1011. Move the radix point one place to the right: .1011 So the exponent is -1: 011 in excess 3 Giving us: 0 011 1011 ? What is 10111100 in decimal? Split it apart into its pieces: 1 011 1100 The sign is 1 or negative The exponent is 011 or -1 The mantissa is 1100. Move the radix one place to the left: .01100 giving us 3/8 Our number is -3/8 ? What is 01011010? Split it apart into its pieces: 0 101 1010 The sign is 0 or positive The exponent is 101 or +1 The mantissa is 1010. Move the radix one place to the right: 1.010 giving us 1 1/4Our number is +1 1/4 Numbering systems answer key16^3 (4096)16^2(256)16^1 (16)16^0 (1)equationanswer1E2??"E" (14x16)= 224"2" (2x1)=2224+262987?"9" (9x256) = 2304"8" (8x16) = 128"7" (7x1)=7 2304+128+724393FFF?"F" (15x256) = 3840"F" (15x16) = 240"F" (15x1)=153840+240+1540954A4??"A" (10x16) = 160"4" (4x1)=4160+41645CDD3"C" (12x4096)=49152"D" (13x256)=3328"D" (13x16)= 208"3" (3x1)=349152+3328+208+35269164 E 8?"4" (4x256)= 1024"E" (14x16)= 224"8" (8x1) = 81024+224+812567AA53"A" (10x4096)=40960"A" (10x256)=2560"5" (5x16)=80"3" (3x1)=340960+2560+80+343603812BB"1" (1x4096)=4096"2" (2x256)=512"B" (11x16)=176"B" (11x1)=114096+512+176+11479591AFF"1" (1x4096)=4096"A" (10x256)=2560"F" (15x16) = 240"F" (15x1)=154096+2560+240+156911Binary addition: try these problems11__1__111_111_1_1__11____11111_1____1010111101111101011101111111001+1111+1101+111+111+1010+1010+11111+1000110011101100011101010010011111111010001Binary subtraction: try these problems10010110011101100011111111011011110-10-11-11-11-100-110-111-101101111010010010101101100Binary multiplication: try these problems10100101110111011x10x11x10x11x10101000110111011+10+1000+1010+1101001011001010100111+110110010001111Convert these to Two's Compliment then solve, all 4 bit:7"0111"6"0110"4"0100"2"0010"1"0001"-5"1011"-1"1111"-6"1010"-4"1100"-5"1011"1"0010"1"0101""1110""1110""1100"Sources: (floating point image) (floating point rep) ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download