Integer NumbersThe Number Bases of IntegersTextbook Chapter 2 +CMPE12 – Fall 2009 03-2Number Systems Unary, or marks: /////// = 7 /////// + ////// = ///////////// Grouping lead to Roman Numerals: VII + V = VVII = XII Better: Arabic Numerals: 7 + 5 = 12 = 1·10 + 2CMPE12 – Fall 2009 03-3 The value represented by a digit depends on its positionin the number. Ex: 1832Positional Number SystemCMPE12 – Fall 2009 03-4Number = (di·bp)i=0∑num digitsPositional Number Systems Select a number as the base b Define an alphabet of b–1 symbols plus a symbol for zero to represent all numbers Use an ordered sequence of 2 or more digits dto represent numbers The represented number is the sum of all digits, each multiplied by b to the power of the digit‟s position pCMPE12 – Fall 2009 03-5 First used over 4000 years ago in Mesopotamia Base 60 (Sexagesimal), alphabet: 0..59, written as 60 different symbols But the Babylonians used only two symbols, 1 and 10, and didn‟t have the zero Needed context to tell 1 from 60! Example 5,4560=Sexagesimal: A Positional Number SystemCMPE12 – Fall 2009 03-6Babylonian NumbersCMPE12 – Fall 2009 03-7Arabic/Indic Numerals Base (or radix): 10 (decimal) The alphabet (digits or symbols) is 0..9 We use the Arabic symbols for the 10 digits Has the ZERO Numerals introduced to Europe by Leonardo Fibonacci in his Liber Abaci In 1202 So useful!CMPE12 – Fall 2009 03-8Arabic/Indic Numerals The Italian mathematician Leonardo Fibonacci Also known for the Fibonacci sequence 1, 1, 2, 3, 5, 8, 13, 21CMPE12 – Fall 2009 03-9Base ConversionThree cases:I. From any base b to base 10II. From base 10 to any base bIII. From any base b to any other base cCMPE12 – Fall 2009 03-10•Base (radix): b•Digits (symbols): 0 … (b – 1)•Sn-1Sn-2….S2S1S0Use summation to transform any base to decimalValue = Σ (Sibi)n-1i=0From Base b to Base 10CMPE12 – Fall 2009 03-11From Base b to Base 10 Example: 12345 = ?10CMPE12 – Fall 2009 03-12From Base 10 to Base b Use successive divisions Remember the remainders Divide again with the quotientsCMPE12 – Fall 2009 03-13From Base 10 to Base b Example: 201010 = ?5CMPE12 – Fall 2009 03-14From Base b to Base c Use a known intermediate base The easiest way is to convert from base b to base 10 first, and then from 10 to c  Or, in some cases, it is easier to use base 2 as the intermediate base (we‟ll see them soon)CMPE12 – Fall 2009 03-15Roman MultiplicationXXXIII (33 in decimal)XII (12 in decimal)--------------CMPE12 – Fall 2009 03-16Positional Multiplication1135425---------------------------(a lot easier!)CMPE12 – Fall 2009 03-17Numbers for Computers There are many ways to represent a number Representation does not affect computation result Representation affects difficulty of computing results Computers need a representation that works with (fast) electronic circuits Positional numbers work great with 2-state devices Which base should we use for computers?CMPE12 – Fall 2009 03-18Binary Number System Base (radix): 2 Digits (symbols): 0, 1 Binary Digits, or bits Example:  10012=  110002=CMPE12 – Fall 2009 03-19Octal Number System Base (radix): 8 Digits (symbols): 0, 1, 2, 3, 4, 5, 6, 7 3458=  10018=  In C, octal numbers are represented with a leading 0 (0345 or 01001).CMPE12 – Fall 2009 03-20Hexadecimal Number System Base (radix): 16 Digits (symbols): 0-9, A–F (a-f) In C: leading “0x” (e.g., 0xa3) In LC-3: leading “x” (e.g., “x3000”) Hexadecimal is also known as “hex” for shortHex DecimalA 10B 11C 12D 13E 14F 15CMPE12 – Fall 2009 03-21Examples of Converting Hex to Decimal A316=  3E816=CMPE12 – Fall 2009 03-22Decimal To Binary Conversion: Method 1 Divide decimal value by 2 until the value is 0 Example: 44410 Divide 444 by 2; what is the remainder? Divide 222 by 2; what is the remainder? … Result is 0: done Write the remainders starting from the least significant position (the right to the left)CMPE12 – Fall 2009 03-23Decimal To Binary Conversion: Method 2 Know your powers of two and subtract… 256 128 64 32 16 8 4 2 1 Example: 6110 What is the biggest power of two that fits? What is the remainder? What fits? What is the remainder? …  What is the binary representation?CMPE12 – Fall 2009 03-24Knowing The Powers Of Two Know them in your sleep20212223242526272829210CMPE12 – Fall 2009 03-25Binary to Octal Conversion Group into 3 starting at least significant bit Why 3? Add leading 0 as needed  Why not trailing 0s? Write one octal digit for each groupCMPE12 – Fall 2009 03-26Binary to Octal Conversion: Examples 100 010 111 (binary)___________________ (octal) 10 101 110 (binary)___________________ (octal)CMPE12 – Fall 2009 03-27Octal to Binary Conversion Write down the 3-bit binary code for each octal digit Example: 047Octal Binary0 0001 0012 0103 0114 1005 1016 1107 111CMPE12 – Fall 2009 03-28Binary to Hex Conversion Group into 4 starting at least significant bit Why 4? Add leading 0 if needed Write one hex digit for each groupCMPE12 – Fall 2009 03-29Binary to Hex Conversion: Examples 1001 1110 0111 0000 (binary)___________________ (hex) 0001 1111 1010 0011 (binary)___________________ (hex)CMPE12 – Fall 2009 03-30Hex to Binary Conversion Write down the 4-bit binary code for each hex digit Example: 0x 3 9 c 8Hex Bin Hex Bin0 0000 8 10001 0001 9 10012 0010 a 10103 0011 b 10114 0100 c 11005 0101 d 11016 0110 e 11107 0111 f 1111CMPE12 – Fall 2009 03-31Conversion TableDecimal Hexadecimal Octal Binary0 0 0 00001 1 1 00012 2 2 00103 3 3 00114 4 4 01005 5 5 01016 6 6 01107 7 7 01118 8 10 10009 9 11 100110 A 12 101011 B 13 101112 C 14 110013 D 15 110114 E 16 111015 F 17 1111CMPE12 – Fall 2009 03-32More Conversions Hex → Octal Do it in 2 steps Hex → binary → octal Decimal → Hex Do it in 2 steps Decimal → binary → hex So why use hex and octal and not just binary and decimal?CMPE12 – Fall 2009 03-33Largest Number What is the largest number that we can represent in n digits… In base 10? In base 2? In octal? In hex?  In base 7? In base b? How many different numbers can we represent with n digits in