**CH09 Computer Arithmetic**• CPU combines of ALU and Control Unit, this chapter discusses ALU • The Arithmetic and Logic Unit (ALU) • Number Systems • Integer Representation • Integer Arithmetic • Floating-Point Representation • Floating-Point Arithmetic TECH Computer Science CH08**Arithmetic & Logic Unit**• Does the calculations • Everything else in the computer is there to service this unit • Handles integers • May handle floating point (real) numbers • May be separate FPU (maths co-processor) • May be on chip separate FPU (486DX +)**Number Systems**• ALU does calculations with binary numbers • Decimal number system • Uses 10 digits (0,1,2,3,4,5,6,7,8,9) • In decimal system, a number 84, e.g., means84 = (8x10) + 3 • 4728 = (4x1000)+(7x100)+(2x10)+8 • Base or radix of 10: each digit in the number is multiplied by 10 raised to a power corresponding to that digit’s position • E.g. 83 = (8x101)+ (3x100) • 4728 = (4x103)+(7x102)+(2x101)+(8x100)**Decimal number system…**• Fractional values, e.g. • 472.83=(4x102)+(7x101)+(2x100)+(8x10-1)+(3x10-2) • In general, for the decimal representation ofX = {… x2x1x0.x-1x-2x-3 … }X = i xi10i**Binary Number System**• Uses only two digits, 0 and 1 • It is base or radix of 2 • Each digit has a value depending on its position: • 102 = (1x21)+(0x20) = 210 • 112 = (1x21)+(1x20) = 310 • 1002 = (1x22)+ (0x21)+(0x20) = 410 • 1001.1012 = (1x23)+(0x22)+ (0x21)+(1x20) +(1x2-1)+(0x2-2)+(1x2-3) = 9.62510**Decimal to Binary conversion**• Integer and fractional parts are handled separately, • Integer part is handled by repeating division by 2 • Factional part is handled by repeating multiplication by 2 • E.g. convert decimal 11.81 to binary • Integer part 11 • Factional part .81**Decimal to Binary conversion, e.g. //**• e.g. 11.81 to 1011.11001 (approx) • 11/2 = 5 remainder 1 • 5/2 = 2 remainder 1 • 2/2 = 1 remainder 0 • 1/2 = 0 remainder 1 • Binary number 1011 • .81x2 = 1.62 integral part 1 • .62x2 = 1.24 integral part 1 • .24x2 = 0.48 integral part 0 • .48x2 = 0.96 integral part 0 • .96x2 = 1.92 integral part 1 • Binary number .11001 (approximate)**Hexadecimal Notation:**• command ground between computer and Human • Use 16 digits, (0,1,3,…9,A,B,C,D,E,F) • 1A16 = (116 x 161)+(A16 x 16o) = (110 x 161)+(1010 x 160)=2610 • Convert group of four binary digits to/from one hexadecimal digit, • 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; • e.g. • 1101 1110 0001. 1110 1101 = DE1.DE**Integer Representation (storage)**• Only have 0 & 1 to represent everything • Positive numbers stored in binary • e.g. 41=00101001 • No minus sign • No period • How to represent negative number • Sign-Magnitude • Two’s compliment**Sign-Magnitude**• Left most bit is sign bit • 0 means positive • 1 means negative • +18 = 00010010 • -18 = 10010010 • Problems • Need to consider both sign and magnitude in arithmetic • Two representations of zero (+0 and -0)**Two’s Compliment (representation)**• +3 = 00000011 • +2 = 00000010 • +1 = 00000001 • +0 = 00000000 • -1 = 11111111 • -2 = 11111110 • -3 = 11111101**Benefits**• One representation of zero • Arithmetic works easily (see later) • Negating is fairly easy (2’s compliment operation) • 3 = 00000011 • Boolean complement gives 11111100 • Add 1 to LSB 11111101**Range of Numbers**• 8 bit 2s compliment • +127 = 01111111 = 27 -1 • -128 = 10000000 = -27 • 16 bit 2s compliment • +32767 = 011111111 11111111 = 215 - 1 • -32768 = 100000000 00000000 = -215**Conversion Between Lengths**• Positive number pack with leading zeros • +18 = 00010010 • +18 = 00000000 00010010 • Negative numbers pack with leading ones • -18 = 10010010 • -18 = 11111111 10010010 • i.e. pack with MSB (sign bit)**Integer Arithmetic: Negation**• Take Boolean complement of each bit, I.e. each 1 to 0, and each 0 to 1. • Add 1 to the result • E.g. +3 = 011 • Bitwise complement = 100 • Add 1 • = 101 • = -3**Negation Special Case 1**• 0 = 00000000 • Bitwise not 11111111 • Add 1 to LSB +1 • Result 1 00000000 • Overflow is ignored, so: • - 0 = 0 OK!**Negation Special Case 2**• -128 = 10000000 • bitwise not 01111111 • Add 1 to LSB +1 • Result 10000000 • So: • -(-128) = -128 NO OK! • Monitor MSB (sign bit) • It should change during negation • >> There is no representation of +128 in this case. (no +2n)**Addition and Subtraction**• Normal binary addition • 0011 0101 1100 • +0100 +0100 +1111 • -------- ---------- ------------ • 0111 1001 = overflow 11011 • Monitor sign bit for overflow (sign bit change as adding two positive numbers or two negative numbers.) • Subtraction: Take twos compliment of subtrahend then add to minuend • i.e. a - b = a + (-b) • So we only need addition and complement circuits**Multiplication**• Complex • Work out partial product for each digit • Take care with place value (column) • Add partial products**Multiplication Example**• (unsigned numbers e.g.) • 1011 Multiplicand (11 dec) • x 1101 Multiplier (13 dec) • 1011 Partial products • 0000 Note: if multiplier bit is 1 copy • 1011 multiplicand (place value) • 1011 otherwise zero • 10001111 Product (143 dec) • Note: need double length result**Multiplying Negative Numbers**• The previous method does not work! • Solution 1 • Convert to positive if required • Multiply as above • If signs of the original two numbers were different, negate answer • Solution 2 • Booth’s algorithm**Division**• More complex than multiplication • However, can utilize most of the same hardware. • Based on long division**Division of Unsigned Binary Integers**Quotient 00001101 Divisor 1011 10010011 Dividend 1011 001110 Partial Remainders 1011 001111 1011 Remainder 100**Real Numbers**• Numbers with fractions • Could be done in pure binary • 1001.1010 = 24 + 20 +2-1 + 2-3 =9.625 • Where is the binary point? • Fixed? • Very limited • Moving? • How do you show where it is?**Floating Point**• +/- .significand x 2exponent • Point is actually fixed between sign bit and body of mantissa • Exponent indicates place value (point position) Biased Exponent Significand or Mantissa Sign bit**Signs for Floating Point**• Exponent is in excess or biased notation • e.g. Excess (bias) 127 means • 8 bit exponent field • Pure value range 0-255 • Subtract 127 to get correct value • Range -127 to +128 • The relative magnitudes (order) of the numbers do not change. • Can be treated as integers for comparison.**Normalization //**• FP numbers are usually normalized • i.e. exponent is adjusted so that leading bit (MSB) of mantissa is 1 • Since it is always 1 there is no need to store it • (c.f. Scientific notation where numbers are normalized to give a single digit before the decimal point • e.g. 3.123 x 103)**FP Ranges**• For a 32 bit number • 8 bit exponent • +/- 2256 1.5 x 1077 • Accuracy • The effect of changing lsb of mantissa • 23 bit mantissa 2-23 1.2 x 10-7 • About 6 decimal places**IEEE 754**• Standard for floating point storage • 32 and 64 bit standards • 8 and 11 bit exponent respectively • Extended formats (both mantissa and exponent) for intermediate results • Representation: sign, exponent, faction • 0: 0, 0, 0 • -0: 1, 0, 0 • Plus infinity: 0, all 1s, 0 • Minus infinity: 1, all 1s, 0 • NaN; 0 or 1, all 1s, =! 0**FP Arithmetic +/-**• Check for zeros • Align significands (adjusting exponents) • Add or subtract significands • Normalize result**FP Arithmetic x/**• Check for zero • Add/subtract exponents • Multiply/divide significands (watch sign) • Normalize • Round • All intermediate results should be in double length storage**Exercises**• Read CH 8, IEEE 754 on IEEE Web site • Email to: choi@laTech.edu • Class notes (slides) online at:www.laTech.edu/~choi