計算機組成與結(jié)構(gòu)：第二部分-程序和數(shù)據(jù)的機器級表達 02-整數(shù)

第2章信息的表示與處理

——整數(shù)

計算機組成與結(jié)構(gòu)

2016年3月主講教師Today:IntegersIntegersRepresentation:unsignedandsignedConversion,castingExpanding,truncatingAddition,negation,multiplication,shiftingSummaryRepresentationsinmemory,pointers,stringsC中典型整型數(shù)據(jù)的取值范圍(32位機)C數(shù)據(jù)類型最小值最大值char-128127unsignedchar0255short-3276832767unsignedshort065535int-21474836482147483647unsigned[int]04294967295long-21474836482147483647unsignedlong04294967295longlong-92233720368547758089223372036854775807unsignedlonglong018446744073709551615C中典型整型數(shù)據(jù)的取值范圍(64位機)C數(shù)據(jù)類型最小值最大值char-128127unsignedchar0255short-3276832767unsignedshort065535int-21474836482147483647unsigned[int]04294967295long-92233720368547758089223372036854775807unsignedlong018446744073709551605longlong-92233720368547758089223372036854775807unsignedlonglong018446744073709551615EncodingIntegersshortintx=15213;shortinty=-15213;Cshort2byteslongSignBitFor2’scomplement,mostsignificantbitindicatessign0fornonnegative1fornegativeUnsignedTwo’sComplementSignBit補碼與十進制相互轉(zhuǎn)換使用的值盒子及示例8位二進制補碼的值盒子例1:-125=-128+2+1例2:-120=-128+8Two-complementEncodingExample(Cont.)x=15213:0011101101101101y=-15213:1100010010010011NumericRangesUnsignedValuesUMin = 0000…0UMax = 2w–1111…1Two’sComplementValuesTMin = –2w–1100…0TMax = 2w–1–1011…1OtherValuesMinus1111…1ValuesforW=168位機16位機unsignedsignedunsignedsigned原碼反碼補碼8位機16位機unsignedsignedunsignedsigned原碼0~255-127~+1270~65535-32767~+32767反碼0~255-127~+1270~65535-32767~+32767補碼0~255-128~+1270~65535-32768~+32767ValuesforDifferentWordSizesObservations|TMin| = TMax+1AsymmetricrangeUMax = 2*TMax+1 CProgramming#include

<limits.h>Declaresconstants,e.g.,ULONG_MAXLONG_MAXLONG_MINValuesplatformspecific

Today:IntegersIntegersRepresentation:unsignedandsignedConversion,castingExpanding,truncatingAddition,negation,multiplication,shiftingSummaryRepresentationsinmemory,pointers,stringsUnsigned&SignedNumericValuesEquivalenceSameencodingsfornonnegativevaluesUniquenessEverybitpatternrepresentsuniqueintegervalueEachrepresentableintegerhasuniquebitencodingCanInvertMappingsU2B(x)=B2U-1(x)BitpatternforunsignedintegerT2B(x)=B2T-1(x)Bitpatternfortwo’scompintegerXB2T(X)B2U(X)0000000011001020011301004010150110601117–88–79–610–511–412–313–214–1151000100110101011110011011110111101234567T2UT2BB2UTwo’sComplementUnsignedMaintainSameBitPatternxuxXMappingBetweenSigned&UnsignedU2TU2BB2TTwo’sComplementUnsignedMaintainSameBitPatternuxxXMappingsbetweenunsignedandtwo’scomplementnumbers:

keepbitrepresentationsandreinterpretMappingSignedUnsignedSigned01234567-8-7-6-5-4-3-2-1Unsigned0123456789101112131415Bits0000000100100011010001010110011110001001101010111100110111101111U2TT2UMappingSignedUnsignedSigned01234567-8-7-6-5-4-3-2-1Unsigned0123456789101112131415Bits0000000100100011010001010110011110001001101010111100110111101111=+/-16++++++?

?

?-+++++?

?

?uxxw–10RelationbetweenSigned&UnsignedLargenegativeweightbecomesLargepositiveweightT2UT2BB2UTwo’sComplementUnsignedMaintainSameBitPatternxuxX0TMaxTMin–1–20UMaxUMax–1TMaxTMax+12’sComplementRangeUnsignedRangeConversionVisualized2’sComp.UnsignedOrderingInversionNegativeBigPositiveSignedvs.UnsignedinCConstantsBydefaultareconsideredtobesignedintegersUnsignedifhave“U”assuffix0U,4294967259UCastingExplicitcastingbetweensigned&unsignedsameasU2TandT2Uinttx,ty;unsignedux,uy;tx=(int)ux;uy=(unsigned)ty;Implicitcastingalsooccursviaassignmentsandprocedurecallstx=ux;uy=ty; 0 0U== unsigned 1 -1 0< signed 1 -1 0U< unsigned 0 2147483647 -2147483648> signed 1 2147483647U -2147483648> unsigned 0 -1 -2> signed1 (unsigned)-1 -2> unsigned1 2147483647 2147483648U< unsigned 1 2147483647 (int)2147483648< signed0CastingSurprisesExpressionEvaluationIfthereisamixofunsignedandsignedinsingleexpression,

signedvaluesimplicitlycasttounsignedIncludingcomparisonoperations<,>,==,<=,>=ExamplesforW=32:TMIN=-2,147,483,648,TMAX=2,147,483,647Constant1Constant2RelationEvaluationResult 00U -10 -10U 2147483647-2147483647-1 2147483647U-2147483647-1 -1-2 (unsigned)-1-2 21474836472147483648U 2147483647(int)2147483648U

Summary

CastingSigned?Unsigned:BasicRulesBitpatternismaintainedButreinterpretedCanhaveunexpectedeffects:addingorsubtracting2wExpressioncontainingsignedandunsignedintintiscasttounsigned!!Today:IntegersIntegersRepresentation:unsignedandsignedConversion,castingExpanding,truncatingAddition,negation,multiplication,shiftingSummaryRepresentationsinmemory,pointers,stringsSignExtensionTask:Givenw-bitsignedintegerxConvertittow+k-bitintegerwithsamevalueRule:Makekcopiesofsignbit:X

=xw–1,…,xw–1,xw–1,xw–2,…,x0kcopiesofMSB?

?

?X

X

?

?

??

?

??

?

?wwkSignExtensionExampleConvertingfromsmallertolargerintegerdatatypeCautomaticallyperformssignextensionshortintx=15213;intix=(int)x;shortinty=-15213;intiy=(int)y;DecimalHexBinaryx152133B6D0011101101101101ix1521300003B6D00000000000000000011101101101101y-15213C4931100010010010011iy-15213FFFFC49311111111111111111100010010010011Truncating:BasicRulesTruncating(e.g.,unsignedtounsignedshort)Unsigned/signed:bitsaretruncatedResultreinterpretedUnsigned:modoperationSigned:similartomodForsmallnumbersyieldsexpectedbehaviour十六進制無符號補碼原始值截斷值原始值截斷值原始值截斷值00002222919-7B311-5F715-1練習題2.24假設(shè)將一個4位數(shù)值截斷到3位數(shù)值。填寫下表，根據(jù)位模式的無符號和補碼解釋，說明這些截斷對某些情況的結(jié)果。十六進制無符號補碼原始值截斷值原始值截斷值原始值截斷值0000002222229191-71B3113-53F7157-1-1無符號數(shù)截斷，式(2-9)：補碼數(shù)字截斷，式(2-10)：案例1:某32位機器，考慮以下C代碼：1 intx=–1;2 unsignedu=2147483648;34 printf(“x=%u=%d\n”,x,x);5 printf(“u=%u=%d\n”,u,u);在32位機器上運行上述代碼時，它的輸出結(jié)果是什么？為什么？x=4294967295=–1u=2147483648=–2147483648

因為–1的補碼整數(shù)表示為“11…1”，作為32位無符號數(shù)解釋時，其值為232–1=4294967296–1=4294967295。231的無符號數(shù)表示為“100…0”，被解釋為32位帶符號整數(shù)時，其值為最小負數(shù)：–232-1=–231=–2147483648。案例2:1）在有些32位系統(tǒng)上，C表達式-2147483648<2147483647的執(zhí)行結(jié)果為false。Why？2）若定義變量“inti=-2147483648;”，則“i<2147483647”的執(zhí)行結(jié)果為true。Why？3）如果將表達式寫成“-2147483647-1<2147483647”，則結(jié)果會怎樣呢？Why？1）在ISOC90標準下，2147483648被解釋為unsigned類型，因此

“-2147483648<2147483647”按無符號數(shù)比較，10……0B比01……1大，結(jié)果為false。

在ISOC99標準下，2147483648解釋為int類型，因此

“-2147483648<2147483647”按帶符號整數(shù)比較，10……0B比01……1小，結(jié)果為true。2）i<2147483647按int型數(shù)比較，結(jié)果為true。3）-2147483647-1<2147483647按int型比較，結(jié)果為true。Today:IntegersIntegersRepresentation:unsignedandsignedConversion,castingExpanding,truncatingAddition,negation,multiplication,shiftingRepresentationsinmemory,pointers,stringsUnsignedAdditionStandardAdditionFunctionIgnorescarryoutputImplementsModularArithmetics = UAddw(u,v) = (u+v)mod2w?

?

??

?

?uv+?

?

?u+v?

?

?TrueSum:w+1bitsOperands:wbitsDiscardCarry:wbitsUAddw(u,v)Visualizing(Mathematical)IntegerAdditionIntegerAddition4-bitintegersu,vComputetruesumAdd4(u,v)ValuesincreaselinearlywithuandvFormsplanarsurfaceAdd4(u,v)uvVisualizingUnsignedAdditionWrapsAroundIftruesum≥2wAtmostonce02w2w+1UAdd4(u,v)uvTrueSumModularSumOverflowOverflowTwo’sComplementAdditionTAddandUAddhaveIdenticalBit-LevelBehaviorSignedvs.unsignedadditioninC: ints,t,u,v; s=(int)((unsigned)u+(unsigned)v); t=u+vWillgive

s==t?

?

??

?

?uv+?

?

?u+v?

?

?TrueSum:w+1bitsOperands:wbitsDiscardCarry:wbitsTAddw(u,v)TAddOverflowFunctionalityTruesumrequiresw+1bitsDropoffMSBTreatremainingbitsas2’eger–2w–1–1–2w02w–12w–1TrueSumTAddResult1000…01011…10000…00100…00111…1100…0000…0011…1PosOverNegOverCharacterizingTAddFunctionalityTruesumrequiresw+1bitsDropoffMSBTreatremainingbitsas2’eger(NegOver)(PosOver)uv<0>0<0>0NegativeOverflowPositiveOverflowTAdd(u,v)2w2wVisualizing2’sComplementAdditionValues4-bittwo’scomp.Rangefrom-8to+7WrapsAroundIfsum2w–1BecomesnegativeAtmostonceIfsum<–2w–1BecomespositiveAtmostonceTAdd4(u,v)uvPosOverNegOverMultiplicationGoal:ComputingProductofw-bitnumbersx,yEithersignedorunsignedBut,exactresultscanbebiggerthanwbitsUnsigned:upto2wbitsResultrange:0≤x*y≤(2w–1)2=22w–2w+1+1Two’scomplementmin(negative):Upto2w-1bitsResultrange:x*y≥(–2w–1)*(2w–1–1)=–22w–2+2w–1Two’scomplementmax(positive):Upto2wbits,butonlyfor(TMinw)2Resultrange:x*y≤(–2w–1)2=22w–2So,maintainingexactresults…wouldneedtokeepexpandingwordsizewitheachproductcomputedisdoneinsoftware,ifneedede.g.,by“arbitraryprecision”arithmeticpackagesUnsignedMultiplicationinCStandardMultiplicationFunctionIgnoreshighorderwbitsImplementsModularArithmeticUMultw(u,v) =u·vmod2w?

?

??

?

?uv*?

?

?u·v?

?

?TrueProduct:2*wbitsOperands:wbitsDiscardwbits:wbitsUMultw(u,v)?

?

?SignedMultiplicationinCStandardMultiplicationFunctionIgnoreshighorderwbitsSomeofwhicharedifferentforsignedvs.unsignedmultiplicationLowerbitsarethesame?

?

??

?

?uv*?

?

?u·v?

?

?TrueProduct:2*wbitsOperands:wbitsDiscardwbits:wbitsTMultw(u,v)?

?

?Power-of-2MultiplywithShiftOperationu<<k

givesu*2kBothsignedandunsignedExamplesu<<3 == u*8u<<5-u<<3 == u*24MostmachinesshiftandaddfasterthanmultiplyCompilergeneratesthiscodeautomatically?

?

?001000???u2k*u·2kTrueProduct:w+kbitsOperands:wbitsDiscardkbits:wbitsUMultw(u,2k)???k?

?

?000???TMultw(u,2k)000?????? leal (%eax,%eax,2),%eax sall $2,%eaxCompiledMultiplicationCodeCcompilerautomaticallygeneratesshift/addcodewhenmultiplyingbyconstantintmul12(intx){returnx*12;} t<-x+x*2 returnt<<2;CFunctionCompiledArithmeticOperationsExplanationUnsignedPower-of-2DividewithShiftQuotientofUnsignedbyPowerof2u>>k

givesu/2kUseslogicalshift001000???u2k/u/2kDivision:Operands:???k?????????000??????

u/2k???Result:.BinaryPoint0000???0SignedPower-of-2DividewithShiftQuotientofSignedbyPowerof2x>>k

givesx/2kUsesarithmeticshiftRoundswrongdirectionwhenu<0001000???x2k/x/2kDivision:Operands:???k?????????0??????RoundDown(x

/2k)???Result:.BinaryPoint0???CorrectPower-of-2DivideQuotientofNegativeNumberbyPowerof2Wantx/2k(RoundToward0)Computeas(x+2k-1)/2kInC:(x+(1<<k)-1)>>kBiasesdividendtoward0Case1:NoroundingDivisor:Dividend:001000???u2k/

u/2k

???k1???000???1???011???.BinaryPoint1000111???+2k–1???111???1???111???BiasinghasnoeffectCorrectPower-of-2Divide(Cont.)Divisor:Dividend:Case2:Rounding001000???x2k/

x/2k

???k1??????1???011???.BinaryPoint1000111???+2k–1???1??????Biasingadds1tofinalresult???Incrementedby1Incrementedby1 shrl $3,%eaxCompiledUnsignedDivisionCodeUseslogicalshiftforunsignedForJavaUsersLogicalshiftwrittenas>>>unsignedudiv8(unsignedx){returnx/8;} #Logicalshift returnx>>3;CFunctionCompiled