《计算机科学导论》课件Unit 4Data Operations

?计算机科学导论?课件Unit4DataOperations24-1LogicalOperations4-2ArithmeticOperations4-3ShiftOperations4-4ReferencesandRecommendedReadings4-5Summary4-6PracticeSetOUTLINE5LogicalOperationsatbitlevel6Figure4.1LogicaloperationsLogicalOperationsatbitlevel7LogicalOperationsatbitlevelNOToperatorXNOTX0110Table4.1TruthtableforNOToperationTheNOToperatortakesoneinputandproducesoneoutput,whichisthecomplementoftheinput.Table4.1showsthetruthtablefortheNOToperationatbitlevel.Atruthtablelistsallpossibleinputcombinationsalongwiththecorrespondingoutputs.

8LogicalOperationsatbitlevelANDoperatorTable4.2TruthtableforANDoperationXYXANDY000010100111TheANDoperatoracceptstwoinputsandcreatesoneoutput.Foreachpairofinputbits,theresultis1ifandonlyifbothbitsare1;otherwise,theresultis0.Table4.2showsthetruthtablefortheANDoperationatbitlevel.9LogicalOperationsatbitlevelANDoperatorInherentRuleoftheANDOperator:TheANDoperationcanbeusedtoforce(unset)individualbitsinabitstringto0.FromTable4.2,wecanseethatifoneoftheinputbitsis0,theresultisalways0regardlessoftheotherinputbit,whichmeansyoudon’tneedtocheckthecorrespondingbitvalueoftheotherinput.10LogicalOperationsatbitlevelORoperatorTable4.3TruthtableforORoperationXYXORY000011101111TheORoperatoracceptstwoinputsandcreatesoneoutput.Foreachpairofinputbits,theresultis0ifandonlyifbothbitsare0;otherwise,theresultis1.Table4.3showsthetruthtablefortheORoperationatbitlevel.11LogicalOperationsatbitlevelORoperatorInherentRuleoftheOROperator:TheORoperationcanbeusedtoforce(set)individualbitsinabitstringto1.Ifoneoftheinputbitsis1,theresultisalways1regardlessoftheotherinputbit,whichmeansyoudon’tneedtocheckthecorrespondingbitvalueoftheotherinput.12LogicalOperationsatbitlevelXORoperatorTable4.4TruthtableforXORoperationXYXXORY000011101110TheXOR(exclusiveOR)operatoracceptstwoinputsandcreatesoneoutput.Foreachpairofinputbits,theresultis0ifandonlyifbothbitsareequal;otherwise,theresultis1.Table4.4showsthetruthtablefortheXORoperationatbitlevel.13LogicalOperationsatbitlevelXORoperatorTheXORoperatorcanbeusedtoselectivelyinvert(fliporNOT)bitsinabitstring.Ifoneoftheinputbitsis1,theresultisalwaystheinverseoftheotherinputbit.Ifoneoftheinputbitsis0,theresultisexactlythevalueoftheotherinputbit.Actually,theXORoperatorisnotabasicoperator.Wecansimulateitsfunctionalitybyusingthethreebasicoperators.Thefollowingexpressionshowstherelationbetweenthem:14LogicalOperationsatbitlevelXNORoperatorTable4.5TruthtableforXNORoperatorXYXXNORY001010100111TheXNORoperatoracceptstwoinputsandcreatesoneoutput.Foreachpairofinputbits,theresultis0ifandonlyifbothbitsarenotequal;otherwise,theresultis1.Table4.5showsthetruthtablefortheXNORoperationatbitlevel.15LogicalOperationsatbitlevelXNORoperatorLikeXORoperator,theXNORoperatorcanberepresentedbyusingthethreebasicoperators.Thefollowingexpressionshowtherelationbetweenthem:Itisnotabasiclogicaloperatortooanditjustareverse(NOT)ofXOR16LogicalOperationsatbitlevelNANDandNORoperatorTheNAND(ornot-and)operatorappliesANDtoitsinputbitsandtheninvertstheoutputbyapplyingNOT.Foreachpairofinputbits,theresultofapplyingNANDoperatoris0ifandonlyifbothbitsare1;otherwise,theresultis1.Similarly,theNOR(ornot-or)operatorappliesORtoitsinputbitsandtheninvertstheoutputbyapplyingNOT.Foreachpairofinputbits,theresultofapplyingNORoperatoris0ifandonlyifeitherofitsinputbitsare1;otherwise,theresultis1.Theycanberepresentedthroughfollowingexpressions:So,theyarenotbasiclogicaloperatorseither.17LogicalOperationsatbitlevelNANDandNORoperatorTable4.6TruthtableforNANDoperatorXYXNANDY00101110111018LogicalOperationsatbitlevelNANDandNORoperatorTable4.7TruthtableforNORoperatorXYXNORY00101010011019LogicalOperationsatpatternlevelThelogicaloperatorsthatcanbeappliedtoann-bitpatternarethesameasthelogicaloperatorsappliedtoeachindividualinputbit.Therearesomeexamplestohelpusunderstandthisrule.ApplytheNOToperatoronthebitpattern11101010Solution20LogicalOperationsatpatternlevelApplyAND,OR,XOR,XNOR,NOR,andNANDoperatorsonthebitpatterns10101101and01101011Solution21LogicalOperationsatpatternlevelApplyAND,OR,XOR,XNOR,NOR,andNANDoperatorsonthebitpatterns10101101and01101011Solution22LogicalOperationsatpatternlevelApplyAND,OR,XOR,XNOR,NOR,andNANDoperatorsonthebitpatterns10101101and01101011Solution23LogicalOperationsatpatternlevelApplyAND,OR,XOR,XNOR,NOR,andNANDoperatorsonthebitpatterns10101101and01101011Solution24LogicDiagramSymbolLogicoperatorsincludethecorrespondingLDS(LogicDiagramSymbol)andLogicFunctionExpression.IEEEstandardandIECstandardaretwodifferentuniversalstandardsforLDS.IntheIECstandard,thesymbol‘1’meansthattheoneinputmustbeactive.The‘&’representsANDfunction.The‘≥1’indicatesthatatleastoneactiveinputisneededtoactivatetheoutput.The‘=1’denotesthatoneandonlyoneinputmustbeactivetoactivatetheoutput.Andthelastsymbol‘=’impliesthatallinputsmuststandatthesamestate.TheLDSandLogicFunctionExpressionarewidelyusedinDigitalElectronicsandIntegratedCircuit.Table4.8showsthedetails.25LogicDiagramSymbolTable4.8LogicDiagramSymbolandLogicFunctionExpression26LogicDiagramSymbolTable4.8LogicDiagramSymbolandLogicFunctionExpression⊙27ApplicationsWecanmodifyabitpatternwithfourbinarylogicoperators:NOT,AND,OR,andXOR.Thesebinaryoperatorscancomplement,unset,set,orflipthetargetbitpatternwithamask.Themaskisusedtomodifythetargetbitpattern.28ApplicationsAND:UnsettingspecificbitsThemostimportantapplicationofANDoperatoristounset(forceto0)specificbitsinatargetbitpattern.Todothat,wemustuseanunsettingmaskofthesamelengthasofthetargetbitpattern.Inthistechnique,tounsetaspecificbitofthetargetbitpattern,thecorrespondingbitinthemaskissetto0.Otherwise,toleaveabitinthetargetbitpatternunchanged,thecorrespondingbitinthemaskissetto1.Forexample,ifyouwanttounsetthe4rightmostbitsofan8-bitpattern,theunsettingmaskmustbe11110000(Figure4.2).29ApplicationsAND:UnsettingspecificbitsFigure4.2Exampleofunsettingspecificbitsofabitpattern30ApplicationsOR:SettingspecificbitsSimilarly,weuseORoperatortoset(forceto1)specificbitsinatargetbitpattern.Inthistechnique,tosetaspecificbitofthetargetbitpattern,thecorrespondingbitinthesettingmaskissetto1.Otherwise,toleaveabitinthetargetbitpatternunchanged,thecorrespondingbitinthemaskissetto0.AnexampleisshowninFigure4.3.31ApplicationsOR:SettingspecificbitsFigure4.3Exampleofsettingspecificbitsofabitpattern32ApplicationsXOR:FlippingspecificbitsTheXORoperatorisusedtoflipspecificbits(0becomes1andviceversa).TheflipoperationisfunctionallysimilartotheNOToperator.Toflipaspecificbitinthetargetbitpattern,thecorrespondingbitintheflippingmaskissetto1.Otherwise,toleaveabitinthetargetbitpatternunchanged,thecorrespondingbitinthemaskissetto0.Figure4.4showsanexampleofflippingspecificbits.33ApplicationsXOR:FlippingspecificbitsFigure4.4Exampleofflippingspecificbits34ApplicationsXOR:FlippingspecificbitsOtherinterestingapplicationsofXORoperatoraretodoparitycheckofbitstringsandtoverifywhetherbytessentacrossanetworkwerecorruptedandneedretransmission,ortheyweresentwithouterrors.ThereareinterestingapplicationsofXORoperator.XORcanbeusedtoexchangetwonumberswithoutusinganyintermediatevariable.Ifwehavea=10011001andb=10110101,thenaftertakingthreeXORoperations,wewillfinallyexchangethevalueofaandb.35ArithmeticOperationsonintegersArithmeticOperationsonreals4-2ArithmeticOperations36

ArithmeticoperationsonintegersThefourbasicarithmeticoperationsareaddition,subtraction,multiplication,anddivision.Theseoperationscanapplytobothintegersandfloating-pointnumbers.Amongthefourbasicarithmeticoperations,theadditionandsubtractionoperationsarefundamentalandessential.Sowefocusonadditionandsubtractionoperationofintegersinthissectionasmultiplicationanddivisionessentiallyboildownto【归结为】theadditionandsubtraction.Thecorrespondingprocedureofmultiplicationanddivisionoperationscanbefoundinbooksoncomputerarchitecture,suchas“ComputerOrganizationandArchitecture:Designingforperformance37ArithmeticoperationsonintegersAdditionandsubtractionintwo’scomplementAllmoderncomputersrepresentintegersinthetwo’scomplementform.Additionandsubtractionintwo’scomplementaremoreorlessthesameasindecimal.Togetthetwo'scomplementnegativenotationofaninteger,orbinaryrepresentationofanegativenumber,writeoutthenumberinbinary.Theninvertthedigits,andaddonetogettheresult.38ArithmeticoperationsonintegersAdditionandsubtractionintwo’scomplementWhentheresultofbinaryadditionofanytwobitsis2(1plus1is(10)),theresultantbitis0andwepropagatea1tothenextmostsignificantplace.This1iscalledcarry【进位】.Nowwecandefinetherulesforaddingtwointegersintwo’scomplementform:adding2bitsandpropagatingthecarrytothenextcolumnfromrighttoleft.Ifthereisafinalcarryaftertheleftmostcolumnaddition,wecandiscardit.39ArithmeticoperationsonintegersAdditionandsubtractionintwo’scomplement

40ArithmeticoperationsonintegersAddtwonumbersintwo’scomplementformat:(+35)+(+29)=(+64)Solution(+35)and(+29)intwo’scomplementformarerepresentedas00100011and00011101foran8bitmemorylocation.Theresultremainssameforanylocationsize.Theresultis64indecimal.41ArithmeticoperationsonintegersSupposeA=(-30)andB=(34).ShowhowBissubtractedfromA,thatisA–B.

A=(11100010)2B=(00100010)2Solution

1022242ArithmeticoperationsonintegersSupposeA=(-30)andB=(34).ShowhowBissubtractedfromA,thatisA–B.

A=(11100010)2B=(00100010)2SolutionThen，accordingtoA–B=A+(B+1)43ArithmeticoperationsonintegersSupposeA=(-30)andB=(34).ShowhowBissubtractedfromA,thatisA–B.

A=(11100010)2B=(00100010)2SolutionIntheresult,theleftmostbit1indicatesthatthenumberisnegative,sotakeitstwo’scomplementtoget01000000,whichis64indecimal.Finally,addinga–signtotheleft,wehave-64indecimal.244ArithmeticoperationsonintegersSolutionIntegerA=(+127)andB=(+3)arestoredintwo’scomplementform.ShowhowBisaddedtoA.A=(01111111)2,

B=(00000011)2AisaddedtoBandtheresultisstoredinR.Obviously,wegetanerrorhere:A+B=R=-126(=01111110)≠130.Wewilldiscussthisissueinnextsection.45ArithmeticoperationsonintegersOverflowWhenyoutrytostoreavaluethatisoutoftherangeofagivenallocation,anarithmeticoverflowoccurs.It’ssimilartowhathappenedwhenyoutrytopourmilkintoacupmorethanitscapacity.Thecomputeroffersusavarietyof“cups〞withlimitedandfixed“volume〞forstoring“milk〞,whichisnumberhere.46ArithmeticoperationsonintegersOverflowTherearetwokindsofoverflows:positiveoverflowandnegativeoverflow.Whenwerepresentaninteger,intwo’scomplementformusingNbits,therangeofvaluesthatcanberepresentedis.Anegativeoverflowoccurswhenanumberislessthan,andapositiveoverflowhappenswhenanumberisgreaterthan.Figure4.5showsthesetwotypesofoverflows.47ArithmeticoperationsonintegersOverflowFigure4.5Overflow

BacktoExample4.5,thenormalrangeisto,whichis-128to127.Buttheresult(130)oftheadditionoperationisoutofthisrange.Thenpositiveoverflowoccurs.Thereasonthatactualresultis-126butnot130isbecauseofthenaturalfeatureoftwo’scomplementrepresentation.48ArithmeticoperationsonintegersOverflowAswecanseefromFigure4.6,whenwereachthenumber127andadd3to127,thefinalresultis-126ratherthan130.Figure4.6Two’sComplementrepresentation(clockwise)49ArithmeticoperationsonrealsAdditionandsubtractionofreals1. Checkthesigns. a)Ifthesignsaresame,addthenumbersandassignthe commonsigntotheresult. b)Ifthesignsaredifferent,taketheabsolutevalues

ofthenumbers,subtractthesmallerfromthelarger,andusethesignofthelargerfortheresult.Allarithmeticoperationscanbeappliedtorealsstoredinfloating-pointformat.Inthissection,weonlyshowrulesforadditionandsubtractionofreals.Additionandsubtractionoperationrulesforfloating-pointnumberarebasicallythesame.Thebasicstepsareasfollows:50ArithmeticoperationsonrealsAdditionandsubtractionofreals2. Whenconvertingtoscientificnotation,movethedecimalpointstomakesuretheexponentsarethesame.Thismeansiftheexponentsarenotequal,thedecimalpointofthenumberwiththesmallerexponentisshiftedtothelefttomakebothnumbershavingthesameexponent.3. Addorsubtractthemantissas(includingthewholepartandthefractionalpart).4. Normalizetheresultbeforestoringtheresultinmemory.5. Checkforanyoverflowandunderflow.51ArithmeticoperationsonintegersShowhowthecomputerfindstheresultof(+21.75)+(+16.4375)=+38.1875.SolutionA=(+21.75),B=(+16.4375).Theyarestoredinthenormalizedfloating-pointform.Afterde-normalization(shiftingdecimalpointonepositiontotheleftandincrementingtheexponentonce),wehave:52ArithmeticoperationsonintegersShowhowthecomputerfindstheresultof(+21.75)+(+16.4375)=+38.1875.Solution

Becausetheexponentsarethesame,sowedon’tneedtoalign.Weapplyadditionoperationonthecombinationsofsignandmantissadirectly.Thenwehavefollowingresult:53ArithmeticoperationsonintegersShowhowthecomputerfindstheresultof(+21.75)+(+16.4375)=+38.1875.SolutionNowtheresultneedstobenormalized.Wedecrementtheexponentonceandshiftthede-normalizedmantissatotheleftoneposition:SothefinalresultisR=+2132−127×1.001100011=+38.1875,asexpected.54ArithmeticoperationsonrealsUnderflowInthissection,underflowreferstoarithmeticunderfloworfloatingpointunderflow，whichmeansresultofanarithmeticoperationoffloating-pointnumberislessthanthecomputercanactuallystoreinmemory.While,overflowmeansthatanoperationresultisoutofthenormalrangethatanN-bitpatterncanrepresent,notacomputersystem.55ArithmeticoperationsonrealsUnderflowInFigure4.7,thefminNmeanstheminimumpositivenumberthatacomputersystemcanrepresent,whichisanumberveryclosetozeropoint.Then,theinterval(-fminN,fminN),iscalledunderflowgap.Inearlydesignofcomputersystem,anynumberinsidetheunderflowgapwouldbesettozero.Thatkindofprocessiscalled“flush-to-zerounderflow〞.Weusuallyusenaturallogarithmtoavoidarithmeticunderflowissues.Figure4.7Underflowgap

56LogicalshiftoperationsArithmeticshiftoperations4-3ShiftOperations57LogicalshiftoperationsTheshiftoperationisanothercommonoperationonthebitlevel.Therearetwotypesofshiftoperations:logicalshiftoperations,andarithmeticshiftoperations.Inthebinaryrepresentationofsignednumber,theleftmostbitrepresentsthesignofthenumber.Butshiftoperationmaychangethatbit.Soalogicalshiftoperationusuallyisappliedtounsignednumber.Asdescribedbelow,wedistinguishtwokindsoflogicalshiftoperations:logicalshiftandlogicalcircularshift.58LogicalshiftoperationsLogicalshiftFigure4.8LogicalshiftoperationsIntheright-shiftlogicaloperation,wediscardtherightmostbitatfirst,thenshifteverybittotheright,andinserta0bittotheleftmostbitfinally.Theleft-shiftlogicaloperationworksconversely.Figure4.8showsthesetwooperationson8-bitpatterns.59LogicalshiftoperationsLogicalcircularshiftFigure4.9CircularshiftoperationsThecircularright-shiftoperationshiftseverybittotheright.Theleftmostbitisreplacedbytherightmostbit.Thecircularleft-shiftoperationworksconversely.Figure4.9showsthesetwooperationson8-bitpatterns.60LogicalshiftoperationsTakealogicalleft-shiftoperationandcircularleft-shiftoperationonthebitpattern10111100respectively.SolutionForthelogicalleft-shiftoperation,theleftmostbitisdiscardedanda0isinsertedastherightmostbit.61LogicalshiftoperationsTakealogicalleft-shiftoperationandcircularleft-shiftoperationonthebitpattern10111100respectively.SolutionForthecircularleft-shiftoperation,therightmostbitisreplacedbytheleftmostbit.62LogicalshiftoperationsUseacombinationoflogicalandshiftoperationstofindthevalue(0or1)ofthethirdbit(fromlefttoright)inapatternofeightbits.SolutionUsethemask00100000toANDwiththetargetbitstoaccessthethirdbitandsettherestofthebitstozero.Rightshiftingtheresultantpattern5times,wethenhave0000000c.Ifthefinalresultis1,thentheoriginalthirdbitis1.Iftheresultis0,thentheoriginalthirdbitis063ArithmeticshiftoperationsUnlikethelogicshiftoperations,arithmeticshiftoperationsfocusonsignedintegerintwo’scomplementform.Functionally,arithmeticright-shiftoperationdividesanintegerbytwo,whilearithmeticleft-shiftoperationmultipliesanintegerbytwo.Thearithmeticright-shiftoperationshiftseverybittotheright.Theleftmostsignbitretainsandtherightmostbitislost.Thearithmeticleft-shiftoperationshiftseverybittotheleft.TheMostSignificantBit(MSB)【最高有效位】islostanda0isinsertedastherightmostbit.Figure4.10showsthearithmeticshiftoperationson8-bitpatterns.64ArithmeticshiftoperationsFigure4.10Arithmeticshiftoperations65ArithmeticshiftoperationsUseanarithmeticright-shiftoperationonthebitpattern10110000.Thepatternisanintegerintwo’scomplementform.SolutionNotethattheMSBretainsthere.

Wecanseethattheresultis-40,whichisexactlythehalfvalueoforiginalvalue,-80.66ArithmeticshiftoperationsUsearithmeticleft-shiftoperationonthebitpattern11010000.Thepatternisanintegerintwo’scomplementform.SolutionTheoriginalnumberis−48andthenewnumberis−96.Obviously,theoriginalnumberismultipliedbytwo.67DaleNandLewisJ:ComputerScienceIlluminated,Jones&BartlettLearning,2021PattersonDAandHennessyJL:ComputerOrganizationandDesign:TheHardware/SoftwareInterface,MorganKaufmannPublishers,1998BryantREandO’HallaronD:ComputerSystems:AProgrammer’sPerspective,PrenticeHall,2021StallingW:ComputerOrganizationandArchitecture,UpperSaddleRiver,NJ:PrenticeHall,2000FloydTL:DigitalFundamentals,PrenticeHall,2021

4-4ReferencesandRecommendedReadingsFormoredetailsaboutthesubjectdiscussedinthischapter,thefollowingbooksarerecommended.684-5SummaryIntegersarerepresentedinthetwo’scomplementformatinmostcomputers.Thecarryisdiscardedifitisobtainedafteradditionoftheleftmostbits.Justnegatethenumbertobesubtractedandaddedwhenweexecutesubtractionoperationintwo’scomplement.Overflowoccurswhenan