计算机组成与结构：第二部分-程序和数据的机器级表达 02-整数

第2章信息的表示与处理

——整数

计算机组成与结构

2016年3月主讲教师Today:IntegersIntegersRepresentation:unsignedandsignedConversion,castingExpanding,truncatingAddition,negation,multiplication,shiftingSummaryRepresentationsinmemory,pointers,stringsC中典型整型数据的取值范围(32位机)C数据类型最小值最大值char-128127unsignedchar0255short-3276832767unsignedshort065535int-21474836482147483647unsigned[int]04294967295long-21474836482147483647unsignedlong04294967295longlong-92233720368547758089223372036854775807unsignedlonglong018446744073709551615C中典型整型数据的取值范围(64位机)C数据类型最小值最大值char-128127unsignedchar0255short-3276832767unsignedshort065535int-21474836482147483647unsigned[int]04294967295long-92233720368547758089223372036854775807unsignedlong018446744073709551605longlong-92233720368547758089223372036854775807unsignedlonglong018446744073709551615EncodingIntegersshortintx=15213;shortinty=-15213;Cshort2byteslongSignBitFor2’scomplement,mostsignificantbitindicatessign0fornonnegative1fornegativeUnsignedTwo’sComplementSignBit补码与十进制相互转换使用的值盒子及示例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假设将一个4位数值截断到3位数值。填写下表，根据位模式的无符号和补码解释，说明这些截断对某些情况的结果。十六进制无符号补码原始值截断值原始值截断值原始值截断值0000002222229191-71B3113-53F7157-1-1无符号数截断，式(2-9)：补码数字截断，式(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位机器上运行上述代码时，它的输出结果是什么？为什么？x=4294967295=–1u=2147483648=–2147483648

因为–1的补码整数表示为“11…1”，作为32位无符号数解释时，其值为232–1=4294967296–1=4294967295。231的无符号数表示为“100…0”，被解释为32位带符号整数时，其值为最小负数：–232-1=–231=–2147483648。案例2:1）在有些32位系统上，C表达式-2147483648<2147483647的执行结果为false。Why？2）若定义变量“inti=-2147483648;”，则“i<2147483647”的执行结果为true。Why？3）如果将表达式写成“-2147483647-1<2147483647”，则结果会怎样呢？Why？1）在ISOC90标准下，2147483648被解释为unsigned类型，因此

“-2147483648<2147483647”按无符号数比较，10……0B比01……1大，结果为false。

在ISOC99标准下，2147483648解释为int类型，因此

“-2147483648<2147483647”按带符号整数比较，10……0B比01……1小，结果为true。2）i<2147483647按int型数比较，结果为true。3）-2147483647-1<2147483647按int型比较，结果为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