CS/COE0447 Computer Organization & Assembly LanguageTopicsArithmeticBinary Number RepresentationCase 1: Sign MagnitudeCase 2: One’s ComplementCase 3: Two’s ComplementRanges of numbersSign ExtensionSummary2’s Complement ExamplesAdditionSubtractionSigned versus Unsigned OperationsSigned OverflowOverflowOverflow with Unsigned OperationsBranch Instructions: Branching Backwards1-bit AdderImplementing an AdderBoolean Logic formulasLogic GatesImplementation in logic gatesN-bit AdderN-bit Ripple-Carry AdderMultiplicationMultiplication Here – see what book saysStraightforward AlgorithmImplementation 1Implementation 2Implementation 3ExampleBinary DivisionImplementation – Figure 3.10Algorithm (figure 3.11)Algorithm continuedFloating-Point (FP) NumbersBinary Fractions for HumansIEEE 754“Biased” RepresentationSlide 41IEEE 754 ExampleIEEE 754 Encoding RevisitedFP Operations NotesFloating-Point AdditionFloating-Point MultiplicationFloating Point Instructions in MIPSAnother ExampleSlide 49Guard and Round bitsExample (in decimal) With Guard and Round bitsExample (in decimal) Without Guard and Round bits1CS/COE0447Computer Organization & Assembly LanguageChapter 32Topics•Negative binary integers–Sign magnitude, 1’s complement, 2’s complement–Sign extension, ranges, arithmetic•Signed versus unsigned operations•Overflow (signed and unsigned)•Branch instructions: branching backwards•Implementations of addition, multiplication, division •Floating point numbers–Binary fractions–IEEE 754 floating point standard–Operations•underflow•Implementations of addition and multiplication (less detail than for integers)•Floating-point instructions in MIPS•Guard and Round bits3Arithmetic•So far we have studied–Instruction set basics–Assembly & machine language•We will now cover binary arithmetic algorithms and their implementations•Binary arithmetic will provide the basis for the CPU’s “datapath” implementation4Binary Number Representation•We looked at unsigned numbers before–B31B30…B2B1B0–B31231+B30230+…+B222+B121+B020•Now we want to deal with more complicated cases–Negative integers–Real numbers (a.k.a. floating-point numbers)•We’ll start with negative integers–Bit patterns and what they represent…–We’ll see 3 schemes; the 3rd (2’s complement) is used in most computers5Case 1: Sign Magnitude•{sign bit, absolute value (magnitude)}–Sign bit•“0” – positive number•“1” – negative number–EX. (assume 4-bit representation)•0000: 0•0011: 3•1001: -1•1111: -7•1000: -0•Properties–two representations of zero–equal number of positive and negative numbers6Case 2: One’s Complement•((2N-1) – number): To multiply a 1’s Complement number by -1, subtract the number from (2N-1)_unsigned. Or, equivalently (and easily!), simply flip the bits•1CRepOf(A) + 1CRepOf(-A) = 2N-1_unsigned (interesting tidbit)•Let’s assume a 4-bit representation (to make it easy to work with)•Examples: •0011: 3•0110: 6•1001: -6 1111 – 0110 or just flip the bits of 0110•1111: -0 1111 – 0000 or just flip the bits of 0000•1000: -7 1111 – 0111 or just flip the bits of 0111•Properties–Two representations of zero–Equal number of positive and negative numbers7Case 3: Two’s Complement•(2N – number): To multiply a 2’s Complement number by -1, subtract the number from 2N_unsigned. Or, equivalently (and easily!), simply flip the bits and add 1.•2CRepOf(A) + 2CRepOf(-A) = 2N_unsigned (interesting tidbit)•Let’s assume a 4-bit representation (to make it easy to work with)•Examples: •0011: 3•0110: 6•1010: -6 10000 – 0110 or just flip the bits of 0110 and add 1•1111: -1 10000 – 0001 or just flip the bits of 0001 and add 1•1001: -7 10000 – 0111 or just flip the bits of 0111 and add 1•1000: -8 10000 – 1000 or just flip the bits of 1000 and add 1•Properties–One representation of zero: 0000–An extra negative number: 1000 (this is -8, not -0)8Ranges of numbers•Range (min to max) in N bits:–SM and 1C: -2^(N-1) -1 to +2^(N-1) -1–2C: -2^(N-1) to +2^(N-1) -19Sign Extension•#s are often cast into vars with more capacity•Sign extension (in all 3 representations): extend the sign bit to the left, and everything works out•la $t0,0x00400033•addi $t1,$t0, 7•addi $t2,$t0, -7•R[rt] = R[rs] + SignExtImm•SignExtImm = {16{immediate[15]},immediate}10Summary•Issues–# of zeros–Balance (and thus range)–Operations’ implementationCode Sign-Magnitude 1’s Complement 2’s Complement000 +0 +0 +0001 +1 +1 +1010 +2 +2 +2011 +3 +3 +3100 -0 -3 -4101 -1 -2 -3110 -2 -1 -2111 -3 -0 -1112’s Complement Examples•32-bit signed numbers–0000 0000 0000 0000 0000 0000 0000 0000 = 0–0000 0000 0000 0000 0000 0000 0000 0001 = +1–0000 0000 0000 0000 0000 0000 0000 0010 = +2–…–0111 1111 1111 1111 1111 1111 1111 1110 = +2,147,483,646–0111 1111 1111 1111 1111 1111 1111 1111 = +2,147,483,647–1000 0000 0000 0000 0000 0000 0000 0000 = - 2,147,483,648 -2^31–1000 0000 0000 0000 0000 0000 0000 0001 = - 2,147,483,647–1000 0000 0000 0000 0000 0000 0000 0010 = - 2,147,483,646–…–1111 1111 1111 1111 1111 1111 1111 1101 = -3–1111 1111 1111 1111 1111 1111 1111 1110 = -2–1111 1111 1111 1111 1111 1111 1111 1111 = -112Addition•We can do binary addition just as we do decimal arithmetic–Examples in lecture •Can be simpler with 2’s complement (1C as well)–We don’t need to worry about the signs of the operands!–Examples in lecture13Subtraction•Notice that subtraction can be done using addition–A – B = A + (-B)–We know how to negate a number–The hardware used for addition can be used for subtraction with a negating unit at one inputAdd 1Invert (“flip”) the bits14Signed versus Unsigned Operations•“unsigned” operations view the operands as positive numbers, even if the most significant bit is 1•Example: 1100 is 12_unsigned but -4_2C •Example: slt versus sltu –li $t0,-4–li $t1,10–slt $t3,$t0,$t1 $t3 = 1–sltu $t4,$t0,$t1 $t4 = 0 !!15Signed Overflow•Because we use a limited number of bits to represent a number, the result of an operation may not fit  “overflow”•No overflow when–We add two numbers with different signs–We subtract a number with the same sign•Overflow when–Adding two positive numbers yields a negative