3.Arithmetic+for+Computers.ppt

Computer Organization&DesignThe Hardware/Software Interface,2024/2/19,1,Arithmetic for Computers,Arithmetic for Computers,Operations on integersAddition and subtractionMultiplication and divisionWhat about fractions and real numbers?Representation and operations How are overflow scenarios handled?e.g.An operation creates a number bigger than can be representedHow does hardware really multiply and divide numbers?,MIPS Arithmetic Logic Unit(ALU),Must support the Arithmetic/Logic operations of the ISAadd,addi,addiu,addusub,subumult,multu,div,divu sqrtand,andi,nor,or,ori,xor,xori beq,bne,slt,slti,sltiu,sltu,With special handling forsign extend addi,addiu,slti,sltiuzero extend andi,ori,xorioverflow detection add,addi,sub,Computer words are composed of bits;thus words can be represented as binary numbers.What about fractions and other real numbers?What happen if an operations creates a number bigger than can be representedAnd underlying these questions is a mystery:How does hardware really multiply or divide numbers?,3.1 Introduction,2024/2/19,4,Different Representations of Natural NumbersXXVIIRoman numerals(not positional)27Radix-10 or decimal number(positional)110112Radix-2 or binary number(also positional)Fixed-radix positional representation with k digitsNumber N in radix r=(dk1dk2.d1d0)rValue=dk1r k1+dk2r k2+d1r+d0Examples:(11011)2=124+123+022+12+1=27(2103)4=243+142+04+3=147,Positional Number Systems,Binary Numbers,Each binary digit(called bit)is either 1 or 0Bits have no inherent（固有的）meaning,can representUnsigned and signed integersCharactersFloating-point numbersImages,sound,etc.Bit NumberingLeast significant bit(LSB)is rightmost(bit 0)Most significant bit(MSB)is leftmost(bit 7 in an 8-bit number),Converting Binary to Decimal,Each bit represents a power of 2Every binary number is a sum of powers of 2Decimal Value=(dn-1 2n-1)+.+(d1 21)+(d0 20)Binary(10011101)2=27+24+23+22+1=157,Convert Unsigned Decimal to Binary,Repeatedly divide the decimal integer by 2Each remainder is a binary digit in the translated value,37=(100101)2,Hexadecimal Integers,16 Hexadecimal Digits:0 9,A FMore convenient to use than binary numbers,Binary,Decimal,and Hexadecimal Equivalents,Converting Binary to Hexadecimal,Each hexadecimal digit corresponds to 4 binary bitsExample:Convert the 32-bit binary number to hexadecimal1110 1011 0001 0110 1010 0111 1001 0100Solution:,0100,4,1001,9,0111,7,1010,A,0110,6,0001,1,1011,B,1110,E,Multiply each digit by its corresponding power of 16Value=(dn-1 16n-1)+(dn-2 16n-2)+.+(d1 16)+d0Examples:(1234)16=(1 163)+(2 162)+(3 16)+4=Decimal Value 4660(3BA4)16=(3 163)+(11 162)+(10 16)+4=Decimal Value 15268,Converting Hexadecimal to Decimal,Converting Decimal to Hexadecimal,Decimal 422=1A6 hexadecimal,Repeatedly divide the decimal integer by 16Each remainder is a hex digit in the translated value,Integer Storage Sizes,What is the largest 20-bit unsigned integer?Answer:220 1=1,048,575,Storage Sizes,Binary Addition,Start with the least significant bit(rightmost bit)Add each pair of bitsInclude the carry in the addition,if present,(54),(29),(83),1,1,1,0,1,0,1,0,0,1,1,Hexadecimal Addition,Start with the least significant hexadecimal digitsLet Sum=summation of two hex digitsIf Sum is greater than or equal to 16Sum=Sum 16 and Carry=1Example:,A,F,C,D,B,A+B=10+11=21Since 21 16Sum=21 16=5Carry=1,Signed Integers,Several ways to represent a signed numberSign-MagnitudeBiased1s complement2s complementDivide the range of values into 2 equal partsFirst part corresponds to the positive numbers(0)Second part correspond to the negative numbers(0)Focus will be on the 2s complement representationHas many advantages over other representationsUsed widely in processors to represent signed integers,Twos Complement Representation,Positive numbersSigned value=Unsigned valueNegative numbersSigned value=Unsigned value 2nn=number of bitsNegative weight for MSBAnother way to obtain the signed value is to assign a negative weight to most-significant bit=-128+32+16+4=-76,Forming the Twos Complement,Sum of an integer and its 2s complement must be zero:00100100+11011100=00000000(8-bit sum)Ignore Carry,Another way to obtain the 2s complement:Start at the least significant 1Leave all the 0s to its right unchangedComplement all the bits to its left,Binary Value=00100 1 002s Complement=11011 1 00,Sign Bit,Highest bit indicates the sign1=negative0=positive,For Hexadecimal Numbers,check most significant digitIf highest digit is 7,then value is negativeExamples:8A and C5 are negative bytesB1C42A00 is a negative word(32-bit signed integer),Sign Extension,Step 1:Move the number into the lower-significant bitsStep 2:Fill all the remaining higher bits with the sign bitThis will ensure that both magnitude and sign are correctExamplesSign-Extend 10110011 to 16 bitsSign-Extend 01100010 to 16 bitsInfinite 0s can be added to the left of a positive numberInfinite 1s can be added to the left of a negative number,Twos Complement of a Hexadecimal,To form the twos complement of a hexadecimalSubtract each hexadecimal digit from 15Add 1Examples:2s complement of 6A3D=95C2+1=95C32s complement of 92F15AC0=6D0EA53F+1=6D0EA5402s complement of FFFFFFFF=00000000+1=00000001No need to convert hexadecimal to binary,Binary Subtraction,When subtracting A B,convert B to its 2s complementAdd A to(B)0 1 0 0 1 1 0 10 1 0 0 1 1 0 1 0 0 1 1 1 0 1 01 1 0 0 0 1 1 0(2s complement)0 0 0 1 0 0 1 10 0 0 1 0 0 1 1(same result)Final carry is ignored,becauseNegative number is sign-extended with 1sYou can imagine infinite 1s to the left of a negative numberAdding the carry to the extended 1s produces extended zeros,+,borrow:,carry:,1,1,1,1,1,1,1,Hexadecimal Subtraction,When a borrow is required from the digit to the left,thenAdd 16(decimal)to the current digits valueLast Carry is ignored,Borrow:,-,E,2,4,2,1,B,D,2,1,1,1,E,B,D,(same result),Ranges of Signed Integers,For n-bit signed integers:Range is-2n1 to(2n1 1)Positive range:0 to 2n1 1Negative range:-2n1 to-1,Practice:What is the range of signed values that may be stored in 20 bits?,3.2 Addition&subtraction,Adding bit by bit,carries-next digitSubtractionDirectlyAddition of 2s complement,2024/2/19,25,Overflow,The sum of two numbers can exceed any representationThe difference of two numbers can exceed any representation2s complement:Numbers changesign and size,2024/2/19,26,Overflow,General overflow conditions,2024/2/19,27,Carry and Overflow Examples,We can have carry without overflow and vice-versaFour cases are possible(Examples are 8-bit numbers),Carry and Overflow,Carry is important when Adding or subtracting unsigned integersIndicates that the unsigned sum is out of rangeEither maximum unsigned n-bit valueOverflow is important when Adding or subtracting signed integersIndicates that the signed sum is out of rangeOverflow occurs whenAdding two positive numbers and the sum is negativeAdding two negative numbers and the sum is positiveCan happen because of the fixed number of sum bits,Unsigned Integers:n-bit representationSigned Integers:n-bit 2s complement representation,Range,Carry,Borrow,and Overflow,max=2n1,min=0,max=2n-11,min=-2n-1,Overflow,Reaction on overflowIgnore?Reaction of the OSSignalling to application(Ada,Fortran,.)Hardware detection in the ALUGeneration of an exception(interrupt)Save the instruction address(not PC)in special register EPCJump to specific routine in OSCorrect&return to programReturn to program with error codeAbort program,2024/2/19,31,Overflow,Overflows in signed arithmetic instructions cause exceptions:addadd immediatesubtractOverflows in unsigned arithmetic instructions dont cause exceptions:add unsignedadd immediate unsignedSubtract unsignedHandle with care!,2024/2/19,32,Constructing an ALU,Step by step:build a single bit ALU and expand it to the desired widthFirst function:logic AND and OR,2024/2/19,33,A half adder,Sum=a b+a bCarry=a b,2024/2/19,34,A full adder,Accepts a carry inSum=A xor B xor CarryInCarryOut=B CarryIn+A CarryIn+A B,2024/2/19,35,Full adder,Full adder in 2-level design,2024/2/19,36,1 bit ALU,ALUANDORADDCascade Element,2024/2/19,37,