2.pdf

Objectives Understand the fundamentals of numerical data representation and manipulation in digital computers. Master the skill of converting between various radix systems. Understand the fundamental concepts of floating-point representation. Weekly Learning Outcomes 1. POSITIONAL NUMBERING SYSTEMS...

Objectives Understand the fundamentals of numerical data representation and manipulation in digital computers. Master the skill of converting between various radix systems. Understand the fundamental concepts of floating-point representation. Weekly Learning Outcomes 1. POSITIONAL NUMBERING SYSTEMS 2. CONVERTING BETWEEN BASES. 3. SIGNED INTEGER REPRESENTATION Why Binary? Early computer design was decimal Mark I and ENIAC John von Neumann proposed binary data processing (1945) Simplified computer design Used for both instructions and data Natural relationship between on/off switches and calculation using Boolean logic On Off True False Yes No 1 0 Counting and Arithmetic Decimal or base 10 number system Origin: counting on the fingers “Digit” from the Latin word digitus meaning “finger” Base: the number of different digits including zero in the number system Example: Base 10 has 10 digits, 0 through 9 Binary or base 2 Bit (binary digit): 2 digits, 0 and 1 Octal or base 8: 8 digits, 0 through 7 Hexadecimal or base 16: 16 digits, 0 through F Examples: 1010 = A16; 1110 = B16 Keeping Track of the Bits Bits commonly stored and manipulated in groups 8 bits = 1 byte 4 bytes = 1 word (in many systems) Number of bits used in calculations Affects accuracy of results Limits size of numbers manipulated by the computer Numbers: Physical Representation Different numerals, same number of oranges Cave dweller: IIIII Roman: V Arabic: 5 Different bases, same number of oranges 510 1012 123 Number System Roman: position independent Modern: based on positional notation (place value) Decimal system: system of positional notation based on powers of 10. Binary system: system of positional notation based powers of 2 Octal system: system of positional notation based on powers of 8 Hexadecimal system: system of positional notation based powers of 16 Positional Notation: Base 10 527 = 5 x 102 + 2 x 101 + 7 x 100 100’s place 1’s place 10’s place Place 102 101 100 Value 100 10 1 5 x 100 2 x 10 7 x1 500 20 7 Evaluate Sum Positional Notation: Octal 6248 = 40410 64’s place 8’s place 1’s place Place 82 81 80 Value 64 8 1 Evaluate 6 x 64 2x8 4x1 Sum for Base 10 384 16 4 Positional Notation: Hexadecimal 6,70416 = 26,37210 4,096’s place 256’s place 16’s place Place 163 162 161 160 Value 4,096 256 16 1 6x 7 x 256 0 x 16 4x1 1,792 0 4 Evaluate 4,096 Sum for Base 10 24,576 1’s place Positional Notation: Binary 1101 01102 = 21410 Place 27 26 25 24 23 22 21 20 Value 128 64 32 16 8 4 2 1 1 x16 0x8 1x4 1x2 0x1 16 0 4 2 0 Evaluate 1 x 128 1 x 64 0 x 32 Sum for Base 10 128 64 0 Range of Possible Numbers R = BK where R = range B = base K = number of digits Example #1: Base 10, 2 digits R = 102 = 100 different numbers (0…99) Example #2: Base 2, 16 digits R = 216 = 65,536 or 64K 16-bit PC can store 65,536 different number values Decimal Range for Bit Widths Bits Digits Range 1 0+ 4 1+ 8 2+ 10 3 1,024 (1K) 16 4+ 65,536 (64K) 20 6 32 9+ 64 19+ Approx. 1.6 x 1019 128 38+ Approx. 2.6 x 1038 2 (0 and 1) 16 (0 to 15) 256 1,048,576 (1M) 4,294,967,296 (4G) Base or Radix Base: The number of different symbols required to represent any given number The larger the base, the more numerals are required Base 10: Base 2: Base 8: Base 16: 0,1, 2,3,4,5,6,7,8,9 0,1 0,1,2, 3,4,5,6,7 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F Number of Symbols vs. Number of Digits For a given number, the larger the base the more symbols required but the fewer digits needed Example #1: 6516 10110 1458 110 01012 Example #2: 11C16 28410 4348 1 0001 11002 Counting in Base 2 Equivalent Binary 1’s (20) Number 0 0 x 20 0 1 1 x 20 1 Number 8’s (23) 4’s (22) 2’s (21) Decimal 10 1 x 21 0 x 20 2 11 1 x 21 1 x 20 3 100 1 x 22 101 1 x 22 110 1 x 22 1 x 21 111 1 x 22 1 x 21 1000 1 x 23 1001 1 x 23 1010 1 x 23 4 1 x 20 5 6 1 x 20 7 8 1 x 20 1 x 21 9 10 Binary Arithmetic 1 1 1 1 1 + 1 0 0 1 1 0 1 1 0 1 1 0 1 1 0 0 0 0 1 1 Binary Arithmetic Addition Boolean using XOR and AND + 0 1 Multiplication AND Shift 0 1 0 1 1 10 0 1 0 0 0 1 Division x 0 1 Binary Arithmetic: Boolean Logic Boolean logic without performing arithmetic EXCLUSIVE-OR Output is “1” only if either input, but not both inputs, is a “1” AND (carry bit) Output is “1” if and only both inputs are a “1” 1 + 1 1 1 1 1 0 0 1 0 1 0 1 1 0 0 1 1 0 0 1 1 1 0 1 Binary Multiplication 1 1 1 0 1 1 0 1 1 1 0 1 1’s place 0 2’s place 1 1 0 1 0 0 0 0 4’s place (bits shifted to line up with 4’s place of multiplier) 0 1 Result (AND) Converting from Base 10 Powers Table Power Base 8 7 6 5 4 3 2 1 0 2 256 128 64 32 16 8 4 2 1 32,768 4,096 512 64 8 1 256 16 1 8 16 65,536 4,096 From Base 10 to Base 2 4210 = 1010102 Power Base 6 5 4 3 2 1 0 2 64 32 16 8 4 2 1 1 0 1 0 1 0 Integer 42/32 =1 10/16 =0 10/8 =1 2/4 =0 2/2 =1 0/1 =0 Remainder 10 2 0 0 10 2 From Base 10 to Base 2 Base 10 42 Quotient Remainder 2 ) 42 ( 0 Least significant bit 2 ) 21 ( 1 2 ) 10 ( 0 2) 2) 2) Base 2 5 (1 2 (0 1 Most significant bit 101010 From Base 10 to Base 16 5,73510 = 166716 Power Base 4 3 2 1 0 16 65,536 4,096 256 16 1 1 6 6 7 Integer 5,735 /4,096 =1 Remainder 5,735 - 4,096 1,639 –1,536 103 – 96 = 1,639 = 103 =7 1,639 / 256 =6 103 /16 =6 7 From Base 10 to Base 16 Base 10 8,039 Quotient 16 ) 16 ) 16 ) 16 ) 16 ) Base 16 Remainder 8,039 ( 7 Least significant bit 502 ( 6 31 ( 15 1 ( 1 Most significant bit 0 1F67 From Base 8 to Base 10 72638 = 3,76310 Power Sum for Base 10 83 82 81 80 512 64 8 1 x7 x2 x6 x3 3,584 128 48 3 Fractions Number point or radix point Decimal point in base 10 Binary point in base 2 No exact relationship between fractional numbers in different number bases Exact conversion may be impossible Decimal Fractions Move the number point one place to the right Effect: multiplies the number by the base number Example: 139.010 139010 Move the number point one place to the left Effect: divides the number by the base number Example: 139.010 13.910 Fractions: Base 10 and Base 2.258910 Place 10-1 10-2 10-3 10-4 Value 1/10 1/100 1/1000 1/10000 2 x 1/10 5 x 1/100 8 x 1/1000 9 x1/1000.2.05.008.0009 Evaluate Sum.1010112 = 0.67187510 Place 2-1 2-2 2-3 2-4 2-5 2-6 Value 1/2 1/4 1/8 1/16 1/32 1/64 1 x 1/2 0 x 1/4 1x 1/8 0 x 1/16 1 x 1/32 1 x 1/64 0.03125 0.015625 Evaluate Sum.5 0.125 Fractions: Base 10 and Base 2 No general relationship between fractions of types 1/10k and 1/2k Therefore a number representable in base 10 may not be representable in base 2 But: the converse is true: all fractions of the form 1/2k can be represented in base 10 Fractional conversions from one base to another are stopped If there is a rational solution or When the desired accuracy is attained Mixed Number Conversion Integer and fraction parts must be converted separately Radix point: fixed reference for the conversion Digit to the left is a unit digit in every base B0 is always 1 regardless of the base Signed-Integer Representation No obvious direct way to represent the sign in binary notation Options: Sign-and-magnitude representation 1’s complement 2’s complement (most common) Sign-and-Magnitude Use left-most bit for sign 0 = plus; 1 = minus Total range of integers the same Half of integers positive; half negative Magnitude of largest integer half as large Example using 8 bits: Unsigned: 1111 1111 = +255 Signed: 0111 1111 = +127 1111 1111 = -127 Note: 2 values for 0: +0 (0000 0000) and -0 (1000 0000) Difficult Calculation Algorithms Sign-and-magnitude algorithms complex and difficult to implement in hardware Must test for 2 values of 0 Useful with BCD Order of signed number and carry/borrow makes a difference Example: Decimal addition algorithm Addition: 2 Positive Numbers 4 +2 6 Addition: 1 Signed Number 4 -2 2 2 -4 -2 12 -4 8 Complementary Representation Sign of the number does not have to be handled separately Consistent for all different signed combinations of input numbers Two methods Radix: value used is the base number Diminished radix: value used is the base number minus 1 9’s complement: base 10 diminished radix 1’s complement: base 2 diminished radix 9’s Decimal Complement Taking the complement: subtracting a value from a standard basis value Decimal (base 10) system diminished radix complement Radix minus 1 = 10 – 1 9 as the basis 3-digit example: base value = 999 Range of possible values 0 to 999 arbitrarily split at 500 Numbers Representation method Range of decimal numbers Calculation Negative Positive Complement Number itself -499 -000 +0 999 minus number Representation example 999 – 499 500 – 999 499 none 0 Increasing value 499 + 9’s Decimal Complement Necessary to specify number of digits or word size Example: representation of 3-digit number First digit = 0 through 4 First digit = 5 through 9 positive number negative number Conversion to sign-and-magnitude number for 9’s complement 321 remains 321 521: take the complement (999 – 521) = – 478 Choice of Representation Must be consistent with rules of normal arithmetic - (-value) = value If we complement the value twice, it should return to its original value Complement = basis – value Complement twice Basis – (basis – value) = value Modular Addition Counting upward on scale corresponds to addition Example in 9’s complement: does not cross the modulus +250 Representation Number represented 500 649 -499 -350 +250 899 +250 999 0 170 420 499 -100 -000 0 170 420 499 +250 Addition with Wraparound Count to the right to add a negative number Wraparound scale used to extend the range for the negative result Counting left would cross the modulus and give incorrect answer because there are 2 values for 0 (+0 and -0) +699 Representation Number represented 500 999 0 200 499 -499 -000 0 200 499 Number represented 899 999 -499 -100 -000 -300 +699 Wrong Answer!! Representation 500 500 898 999 0 200 499 -499 -101 -000 0 200 499 - 300 Addition with End-around Carry Count to the right crosses the modulus End-around carry Add 2 numbers in 9’s complementary arithmetic If the result has more digits than specified, add carry to the result +300 Representation Number represented 500 799 999 0 -499 -200 -000 0 +300 (1099) 99 499 100 499 799 300 1099 1 100 Overflow Fixed word size has a fixed range size Overflow: combination of numbers that adds to result outside the range End-around carry in modular arithmetic avoids problem Complementary arithmetic: numbers out of range have the opposite sign Test: If both inputs to an addition have the same sign and the output sign is different, an overflow occurred 1’s Binary Complement Taking the complement: subtracting a value from a standard basis value Binary (base 2) system diminished radix complement Radix minus 1 = 2 – 1 1 as the basis Inversion: change 1’s to 0’s and 0’s to 1s Numbers beginning with 0 are positive Numbers beginning with 1 are negative 2 values for zero Example with 8-bit binary numbers Numbers Representation method Range of decimal numbers Calculation Representation example Negative Positive Complement Number itself -12710 -010 Inversion 10000000 11111111 +010 12710 None 00000000 01111111 Conversion between Complementary Forms Cannot convert directly between 9’s complement and 1’s complement Modulus in 3-digit decimal: 999 Positive range 499 Modulus in 8-bit binary: 11111111 or 25510 Positive range 01111111 or 12710 Intermediate step: sign-and-magnitude representation Addition Add 2 positive 8-bit numbers Add 2 8-bit numbers with different signs Take the 1’s complement of 58 (i.e., invert) 0011 1010 1100 0101 0010 1101 = 45 0011 1010 = 0110 0111 = 58 103 0010 1101 = 1100 0101 = 1111 0010 = Invert to get magnitude 45 –58 –13 0000 1101 8+4+1 = 13 Addition with Carry 8-bit number Invert 0000 0010 (210) 1111 1101 Add 9 bits End-around carry 0110 1010 = 1111 1101 = 10110 0111 +1 0110 1000 = 106 –2 104 Subtraction 8-bit number Invert 0101 1010 (9010) 1010 0101 Add 9 bits End-around carry 0110 1010 = 106 -0101 1010 = 90 0110 1010 = 106 –1010 0101 = 90 10000 1111 +1 0001 0000 = 16 Overflow 8-bit number 256 different numbers Positive numbers: 0 to 127 Add Test for overflow 2 positive inputs produced negative result overflow! Wrong answer! 0100 0000 = 64 0100 0001 = 65 1000 0001 -126 0111 1110 Invert to get magnitude 12610 Programmers beware: some high-level languages, e.g., some versions of BASIC, do not check for overflow adequately 10’s Complement Create complementary system with a single 0 Radix complement: use the base for complementary operations Decimal base: 10’s complement Example: Modulus 1000 as the as reflection point Numbers Representation method Range of decimal numbers Calculation Representation example Negative Positive Complement Number itself -500 -001 0 1000 minus number 500 999 499 none 0 499 Examples with 3-Digit Numbers Example 1: 10’s complement representation of 247 247 (positive number) 10’s complement of 227 1000 – 247 = 753 (negative number) Example 2: 10’s complement of 17 1000 – 017 = 983 Example 3: 10’s complement of 777 Negative number because first digit is 7 1000 – 777 = 223 Signed value = -223 Alternative Method for 10’s Complement Based on 9’s complement Example using 3-digit number Note: 1000 = 999 + 1 9’s complement = 999 – value Rewriting 10’s complement = 1000 – value = 999 + 1 – value Or: 10’s complement = 9’s complement + 1 Computationally easier especially when working with binary numbers 2’s Complement Modulus = a base 2 “1” followed by specified number of 0’s For 8 bits, the modulus = 1000 0000 Two ways to find the complement Subtract value from the modulus or invert Numbers Representation method Range of decimal numbers Calculation Representation example Negative Positive Complement Number itself -12810 -110 Inversion 10000000 11111111 +010 12710 None 00000000 01111111 Estimating Integer Size Positive numbers begin with 0 Small negative numbers (close to 0) begin with multiple 0’s 1111 1110 = -2 in 8-bit 2’s complements 1000 0000 = -128, largest negative 2’s complements Invert all 1’s and 0’s and approximate the value Overflow and Carry Conditions Carry flag: set when the result of an addition or subtraction exceeds fixed number of bits allocated Overflow: result of addition or subtraction overflows into the sign bit Exponential Notation Also called scientific notation ▪ 12345 ▪ 12345 x 100 ▪ 0.12345 x 105 ▪ 123450000 x 10-4 4 specifications required for a number 1. 2. 3. 4. Sign (“+” in example) Magnitude or mantissa (12345) Sign of the exponent (“+” in 105) Magnitude of the exponent (5) Plus 5. 6. Base of the exponent (10) Location of decimal point (or other base) radix point Summary of Rules Sign of the mantissa Sign of the exponent -0.35790 x 10-6 Location of decimal point Mantissa Base Exponent Format Specification Predefined format, usually in 8 bits Increased range of values (two digits of exponent) traded for decreased precision (two digits of mantissa) Sign of the mantissa SEEMMMMM 2-digit Exponent 5-digit Mantissa Format Mantissa: sign digit in sign-magnitude format Assume decimal point located at beginning of mantissa Excess-N notation: Complementary notation Pick middle value as offset where N is the middle value Representation Exponent being represented 0 49 50 99 -50 -1 0 49 Increasing value + – Overflow and Underflow Possible for the number to be too large or too small for representation Floating Point Calculations Addition and subtraction Exponent and mantissa treated separately Exponents of numbers must agree Align decimal points Least significant digits may be lost Mantissa overflow requires exponent again shifted right Addition and Subtraction Add 2 floating point numbers 05199520 + 04967850 Align exponents 05199520 0510067850 Add mantissas; (1) indicates a carry (1)0019850 Carry requires right shift 05210019(850) Round 05210020 Check results 05199520 = 0.99520 x 101 = 9.9520 04967850 = 0.67850 x 101 = 0.06785 = 10.01985 In exponential form = 0.1001985 x 102 Multiplication and Division Mantissas: multiplied or divided Exponents: added or subtracted Normalization necessary to Restore location of decimal point Maintain precision of the result Adjust excess value since added twice Example: 2 numbers with exponent = 3 represented in excess-50 notation 53 + 53 =106 Since 50 added twice, subtract: 106 – 50 =56 Multiplication and Division Maintaining precision: Normalizing and rounding multiplication 05220000 04712500  Multiply 2 numbers  Add exponents, subtract offset  Multiply mantissas  Normalize the results 04825000  Round 05210020  Check results x 52 + 47 – 50 = 49 0.20000 x 0.12500 = 0.025000000 05220000 = 0.20000 x 102 04712500 = 0.125 x 10-3 = 0.0250000000 x 10-1  Normalizing and rounding = 0.25000 x 10-2 Floating Point in the Computer Typical floating point format 32 bits provide range ~10-38 to 10+38 8-bit exponent = 256 levels Excess-128 notation 23/24 bits of mantissa: approximately 7 decimal digits of precision IEEE 754 Standard 32-bit Floating Point Value Definition Exponent Mantissa Value 0 ±0 0 0 Not 0 ±2-126 x 0.M 1-254 Any ±2-127 x 1.M 255 ±0 ± 255 not 0 special condition Conversion: Base 10 and Base 2 Two steps Whole and fractional parts of numbers with an embedded decimal or binary point must be converted separately Numbers in exponential form must be reduced to a pure decimal or binary mixed number or fraction before the conversion can be performed Conversion: Base 10 and Base 2 Convert 253.7510 to binary floating point form ▪ Multiply number by 100 25375 ▪ Convert to binary 110 0011 0001 1111 or 1.1000 equivalent 1100 0111 11 x 214 ▪ IEEE Representation Sig n 0 10001101 10001100011111 Excess-127 Exponent = 127 + 14 Mantissa ▪ Divide by binary floating point equivalent of 10010 to restore original decimal value Programming Considerations Integer advantages Easier for computer to perform Potential for higher precision Faster to execute Fewer storage locations to save time and space Most high-level languages provide 2 or more formats Short integer (16 bits) Long integer (64 bits) Programming Considerations Real numbers Variable or constant has fractional part Numbers take on very large or very small values outside integer range Program should use least precision sufficient for the task Packed decimal attractive alternative for business applications Conclusion Computers store data in the form of bits, bytes, and words using the binary numbering system. Hexadecimal numbers are formed using fourbit groups called nibbles. Signed integers can be stored in one’s complement, two’s complement, or signed magnitude representation.