外文翻译 - Java实现蜘蛛纸牌

0外文原献JoshuaBloch,NealGafter著.JavaPuzzlers:Traps,Pitfalls,andCornerCases.JoshuaAddison-WesleyEducationalPublishersInc(2005-06)Puzzle1:OddityThefollowingmethodpurportstodeterminewhetheritssoleargumentisanoddnumber.Doesthemethodwork?publicstaticbooleanisOdd(inti)returni%2=1;Solution1:OddityAnoddnumbercanbedefinedasanintegerthatisdivisibleby2witharemainderof1.Theexpressioni%2computestheremainderwheniisdividedby2,soitwouldseemthatthisprogramoughttowork.Unfortunately,itdoesnt;itreturnsthewrongansweronequarterofthetimeWhyonequarter?Becausehalfofallintvaluesarenegative,andtheisOddmethodfailsforallnegativeoddvalues.Itreturnsfalsewheninvokedonanynegativevalue,whetherevenorodd.ThisisaconsequenceofthedefinitionofJavasremainderoperator(%).Itisdefinedtosatisfythefollowingidentityforallintvaluesaandallnonzerointvaluesb:(a/b)*b+(a%b)=aInotherwords,ifyoudivideabyb,multiplytheresultbyb,andaddtheremainder,youarebackwhereyoustartedJLS15.17.3.Thisidentitymakesperfectsense,butincombinationwithJavastruncatingintegerdivisionoperatorJLS15.17.2,itimpliesthatwhentheremainderoperationreturnsanonzeroresult,ithasthesamesignasitsleftoperand.TheisOddmethodandthedefinitionofthetermoddonwhichitwasbasedbothassumethatallremaindersarepositive.AlthoughthisassumptionmakessenseforsomekindsofdivisionBoxing,Javasremainderoperationisperfectlymatchedtoitsintegerdivisionoperation,whichdiscardsthefractionalpartofitsresult.Wheniisanegativeoddnumber,i%2isequalto-1ratherthan1,sotheisOddmethodincorrectlyreturnsfalse.Topreventthissortofsurprise,testthatyourmethodsbehave1properlywhenpassednegative,zero,andpositivevaluesforeachnumericalparameter.Theproblemiseasytofix.Simplycomparei%2to0ratherthanto1,andreversethesenseofthecomparison:publicstaticbooleanisOdd(inti)returni%2!=0;IfyouareusingtheisOddmethodinaperformance-criticalsetting,youwouldbebetteroffusingthebitwiseANDoperator(&)inplaceoftheremainderoperator:publicstaticbooleanisOdd(inti)return(iThesecondversionmayrunmuchfasterthanthefirst,dependingonwhatplatformandvirtualmachineyouareusing,andisunlikelytorunslower.Asageneralrule,thedivideandremainderoperationsareslowcomparedtootherarithmeticandlogicaloperations.Itsabadideatooptimizeprematurely,butinthiscase,thefasterversionisasclearastheoriginal,sothereisnoreasontoprefertheoriginal.Insummary,thinkaboutthesignsoftheoperandsandoftheresultwheneveryouusetheremainderoperator.Thebehaviorofthisoperatorisobviouswhenitsoperandsarenonnegative,butitisntsoobviouswhenoneorbothoperandsarenegative.Puzzle2:TimeforaChangeConsiderthefollowingwordproblem:Tomgoestotheautopartsstoretobuyasparkplugthatcosts$1.10,butallhehasinhiswalletaretwo-dollarbills.Howmuchchangeshouldhegetifhepaysforthesparkplugwithatwo-dollarbill?Hereisaprogramthatattemptstosolvethewordproblem.Whatdoesitprint?publicclassChangepublicstaticvoidmain(Stringargs)System.out.println(2.00-1.10);2Solution2:TimeforaChangeNaively,youmightexpecttheprogramtoprint0.90,buthowcoulditknowthatyouwantedtwodigitsafterthedecimalpoint?Ifyouknowsomethingabouttherulesforconvertingdoublevaluestostrings,whicharespecifiedbythedocumentationforDouble.toStringJava-API,youknowthattheprogramprintstheshortestdecimalfractionsufficienttodistinguishthedoublevaluefromitsnearestneighbor,withatleastonedigitbeforeandafterthedecimalpoint.Itseemsreasonable,then,thattheprogramshouldprint0.9.Reasonable,perhaps,butnotcorrect.Ifyourantheprogram,youfoundthatitprints0.8999999999999999.Theproblemisthatthenumber1.1cantberepresentedexactlyasadouble,soitisrepresentedbytheclosestdoublevalue.Theprogramsubtractsthisvaluefrom2.Unfortunately,theresultofthiscalculationisnottheclosestdoublevalueto0.9.Theshortestrepresentationoftheresultingdoublevalueisthehideousnumberthatyouseeprinted.Moregenerally,theproblemisthatnotalldecimalscanberepresentedexactlyusingbinaryfloating-point.Ifyouareusingrelease5.0oralaterrelease,youmightbetemptedtofixtheprogrambyusingtheprintffacilitytosettheprecisionoftheoutput:/Poorsolution-stillusesbinaryfloating-point!System.out.printf(%.2f%n,2.00-1.10);Thisprintstherightanswerbutdoesnotrepresentageneralsolutiontotheunderlyingproblem:Itstillusesdoublearithmetic,whichisbinaryfloating-point.Floating-pointarithmeticprovidesgoodapproximationsoverawiderangeofvaluesbutdoesnotgenerallyyieldexactresults.Binaryfloating-pointisparticularlyill-suitedtomonetarycalculations,asitisimpossibletorepresent0.1oranyothernegativepowerof10exactlyasafinite-lengthbinaryfractionEJItem31.Onewaytosolvetheproblemistouseanintegraltype,suchasintorlong,andtoperformthecomputationincents.Ifyougothisroute,makesuretheintegraltypeislargeenoughtorepresentallthevaluesyouwilluseinyourprogram.Forthispuzzle,intisample.Hereishowtheprintlnlooksifwerewriteitusingintvaluestorepresentmonetaryvaluesincents.Thisversionprints90cents,whichistherightanswer:3System.out.println(200-110)+cents);AnotherwaytosolvetheproblemistouseBigDecimal,whichperformsexactdecimalarithmetic.ItalsointeroperateswiththeSQLDECIMALtypeviaJDBC.Thereisonecaveat:AlwaysusetheBigDecimal(String)constructor,neverBigDecimal(double).Thelatterconstructorcreatesaninstancewiththeexactvalueofitsargument:newBigDecimal(.1)returnBigDecimarepresenting0.1000000000000000055511151231257827021181583404541015625.UsingBigDecimalcorrectly,theprogramprintstheexpectedresultof0.90:importjava.math.BigDecimal;publicclassChangepublicstaticvoidmain(Stringargs)System.out.println(newBigDecimal(2.00).subtract(newBigDecimal(1.10);Thisversionisnotterriblypretty,asJavaprovidesnolinguisticsupportforBigDecimal.CalculationswithBigDecimalarealsolikelytobeslowerthanthosewithanyprimitivetype,whichmightbeanissueforsomeprogramsthatmakeheavyuseofdecimalcalculations.Itisofnoconsequenceformostprograms.Insummary,avoidfloatanddoublewhereexactanswersarerequired;formonetarycalculations,useint,long,orBigDecimal.Forlanguagedesigners,considerprovidinglinguisticsupportfordecimalarithmetic.Oneapproachistoofferlimitedsupportforoperatoroverloading,sothatarithmeticoperatorscanbemadetoworkwithnumericalreferencetypes,suchasBigDecimal.Anotherapproachistoprovideaprimitivedecimaltype,asdidCOBOLandPL/I.Puzzle3:LongDivisionThispuzzleiscalledLongDivisionbecauseitconcernsaprogramthatdividestwolongvalues.Thedividendrepresentsthenumberofmicrosecondsinaday;thedivisor,thenumberofmillisecondsinaday.Whatdoestheprogramprint?publicclassLongDivision4publicstaticvoidmain(Stringargs)finallongMICROS_PER_DAY=24*60*60*1000*1000;finallongMILLIS_PER_DAY=24*60*60*1000;System.out.println(MICROS_PER_DAY/MILLIS_PER_DAY);Solution3:LongDivisionThispuzzleseemsreasonablystraightforward.Thenumberofmillisecondsperdayandthenumberofmicrosecondsperdayareconstants.Forclarity,theyareexpressedasproducts.Thenumberofmicrosecondsperdayis(24hours/day60minutes/hour60seconds/minute1,000milliseconds/second1,000microseconds/millisecond).Thenumberofmillisecondsperdaydiffersonlyinthatitismissingthefinalfactorof1,000.Whenyoudividethenumberofmicrosecondsperdaybythenumberofmillisecondsperday,allthefactorsinthedivisorcancelout,andyouareleftwith1,000,whichisthenumberofmicrosecondspermillisecond.Boththedivisorandthedividendareoftypelong,whichiseasilylargeenoughtoholdeitherproductwithoutoverflow.Itseems,then,thattheprogrammustprint1000.Unfortunately,itprints5.Whatexactlyisgoingonhere?TheproblemisthatthecomputationoftheconstantMICROS_PER_DAYdoesoverflow.Althoughtheresultofthecomputationfitsinalongwithroomtospare,itdoesntfitinanint.Thecomputationisperformedentirelyinintarithmetic,andonlyafterthecomputationcompletesistheresultpromotedtoalong.Bythen,itstoolate:Thecomputationhasalreadyoverflowed,returningavaluethatistoolowbyafactorof200.ThepromotionfrominttolongisawideningprimitiveconversionJLS5.1.2,whichpreservesthe(incorrect)numericalvalue.ThisvalueisthendividedbyMILLIS_PER_DAY,whichwascomputedcorrectlybecauseitdoesfitinanint.Theresultofthisdivisionis5.Sowhyisthecomputationperformedinintarithmetic?Becauseallthefactorsthataremultipliedtogetherareintvalues.Whenyoumultiplytwointvalues,yougetanotherintvalue.Javadoesnothavetargettyping,alanguagefeaturewhereinthetypeofthevariablein5whicharesultistobestoredinfluencesthetypeofthecomputation.Itseasytofixtheprogrambyusingalongliteralinplaceofanintasthefirstfactorineachproduct.Thisforcesallsubsequentcomputationsintheexpressiontobedonewithlongarithmetic.AlthoughitisnecessarytodothisonlyintheexpressionforMICROS_PER_DAY,itisgoodformtodoitinbothproducts.Similarly,itisntalwaysnecessarytousealongasthefirstvalueinaproduct,butitisgoodformtodoso.Beginningbothcomputationswithlongvaluesmakesitclearthattheywontoverflow.Thisprogramprints1000asexpected:publicclassLongDivisionpublicstaticvoidmain(Stringargs)finallongMICROS_PER_DAY=24L*60*60*1000*1000;finallongMILLIS_PER_DAY=24L*60*60*1000;System.out.println(MICROS_PER_DAY/MILLIS_PER_DAY);Thelessonissimple:Whenworkingwithlargenumbers,watchoutforoverflowitsasilentkiller.Justbecauseavariableislargeenoughtoholdaresultdoesntmeanthatthecomputationleadingtotheresultisofthecorrecttype.Whenindoubt,performtheentirecomputationusinglongarithmetic.Thelessonforlanguagedesignersisthatitmaybeworthreducingthelikelihoodofsilentoverflow.Thiscouldbedonebyprovidingsupportforarithmeticthatdoesnotoverflowsilently.Programscouldthrowanexceptioninsteadofoverflowing,asdoesAda,ortheycouldswitchtoalargerinternalrepresentationautomaticallyasrequiredtoavoidoverflow,asdoesLisp.Bothoftheseapproachesmayhaveperformancepenaltiesassociatedwiththem.Anotherwaytoreducethelikelihoodofsilentoverflowistosupporttargettyping,butthisaddssignificantcomplexitytothetypesystemModula-31.4.8.Puzzle4:ItsElementaryOK,sothelastpuzzlewasabittricky,butitwasaboutdivision.Everyoneknowsthatdivisionistough.Thisprograminvolvesonlyaddition.Whatdoesitprint?6publicclassElementarypublicstaticvoidmain(Stringargs)System.out.println(12345+5432l);Solution4:ItsElementaryOnthefaceofit,thislookslikeaneasypuzzlesoeasythatyoucansolveitwithoutpencilorpaper.Thedigitsoftheleftoperandoftheplusoperatorascendfrom1to5,andthedigitsoftherightoperanddescend.Therefore,thesumsofcorrespondingdigitsremainconstant,andtheprogrammustsurelyprint66666.Thereisonlyoneproblemwiththisanalysis:Whenyouruntheprogram,itprints17777.CoulditbethatJavahasanaversiontoprintingsuchabeastlynumber?Somehowthisdoesntseemlikeaplausibleexplanation.Thingsareseldomwhattheyseem.Takethisprogram,forinstance.Itdoesntsaywhatyouthinkitdoes.Takeacarefullookatthetwooperandsofthe+operator.Weareaddingtheintvalue12345tothelongvalue5432l.Notethesubtledifferenceinshapebetweenthedigit1atthebeginningoftheleftoperandandthelowercaseletterelattheendoftherightoperand.Thedigit1hasanacuteanglebetweenthehorizontalstroke,orarm,andtheverticalstroke,orstem.Thelowercaseletterel,bycontrast,hasarightanglebetweenthearmandthestem.Beforeyoucryfoul,notethatthisissuehascausedrealconfusion.Alsonotethatthepuzzlestitlecontainedahint:ItsEl-ementary;getit?Finally,notethatthereisareallessonhere.Alwaysuseacapitalel(L)inlongliterals,neveralowercaseel(l).Thiscompletelyeliminatesthesourceofconfusiononwhichthepuzzlerelies:System.out.println(12345+5432L);Similarly,avoidusingaloneel(l)asavariablename.Itisdifficulttotellbylookingatthiscodesnippetwhetheritprintsthelistlorthenumber1:/Badcode-usesel(l)asavariablenameListl=newArrayList();l.add(Foo);System.out.println(1);7Insummary,thelowercaseletterelandthedigit1arenearlyidenticalinmosttypewriterfonts.Toavoidconfusingthereadersofyourprogram,neverusealowercaseeltoterminatealongliteralorasavariablename.JavainheritedmuchfromtheCprogramminglanguage,includingitssyntaxforlongliterals.Itwasprobablyamistaketoallowlongliteralstobewrittenwithalowercaseel.Puzzle5:TheJoyofHexThefollowingprogramaddstwohexadecimal,orhex,literalsandprintstheresultinhex.Whatdoestheprogramprint?publicclassJoyOfHexpublicstaticvoidmain(Stringargs)System.out.println(Long.toHexString(0x100000000L+0xcafebabe);Solution5:TheJoyofHexItseemsobviousthattheprogramshouldprint1cafebabe.Afterall,thatisthesumofthehexnumbers10000000016andcafebabe16.Theprogramuseslongarithmetic,whichpermits16hexdigits,soarithmeticoverflowisnotanissue.Yet,ifyourantheprogram,youfoundthatitprintscafebabe,withnoleading1digit.Thisoutputrepresentsthelow-order32bitsofthecorrectsum,butsomehowthethirty-thirdbitgetslost.Itisasiftheprogramweredoingintarithmeticinsteadoflong,orforgettingtoaddthefirstoperand.Whatsgoingonhere?Decimalliteralshaveanicepropertythatisnotsharedbyhexadecimaloroctalliterals:DecimalliteralsareallpositiveJLS3.10.1.Towriteanegativedecimalconstant,youusetheunarynegationoperator(-)incombinationwithadecimalliteral.Inthisway,youcanwriteanyintorlongvalue,whetherpositiveornegative,indecimalform,andnegativedecimalconstantsareclearlyidentifiablebythepresenceofaminussign.Notsoforhexadecimalandoctalliterals.Theycantakeonbothpositiveandnegativevalues.Hexandoctalliteralsarenegativeiftheirhigh-orderbitisset.Inthisprogram,thenumber80xcafebabeisanintconstantwithitshigh-orderbitset,soitisnegative.Itisequivalenttothedecimalvalue-889275714.Theadditionperformedbytheprogramisamixed-typecomputation:Theleftoperandisoftypelong,andtherightoperandisoftypeint.Toperformthecomputation,JavapromotestheintvaluetoalongwithawideningprimitiveconversionJLS5.1.2andaddsthetwolongvalues.Becauseintisasignedintegraltype,theconversionperformssignextension:Itpromotesthenegativeintvaluetoanumericallyequallongvalue.Therightoperandoftheaddition,0xcafebabe,ispromotedtothelongvalue0xffffffffcafebabeL.Thisvalueisthenaddedtotheleftoperand,whichis0x100000000L.Whenviewedasanint,thehigh-order32bitsofthesign-extendedrightoperandare-1,andthehigh-order32bitsoftheleftoperandare1.Addthesetwovaluestogetherandyouget0,whichexplainstheabsenceoftheleading1digitintheprogramsoutput.Hereishowtheadditionlookswhendoneinlonghand.(Thedigitsatthetopoftheadditionarecarries.)11111110xffffffffcafebabeL+0x0000000100000000L0x00000000cafebabeLFixingtheproblemisassimpleasusingalonghexliteraltorepresenttherightoperand.Thisavoidsthedamagingsignextension,andtheprogramprintstheexpectedresultof1cafebabe:publicclassJoyOfHexpublicstaticvoidmain(Stringargs)System.out.println(Long.toHexString(0x100000000L+0xcafebabeL);Thelessonofthispuzzleisthatmixed-typecomputationscanbeconfusing,moresogiventhathexandoctalliteralscantakeonnegativevalueswithoutanexplicitminussign.Toavoidthissortofdifficulty,itisgenerallybesttoavoidmixed-typecomputations.For9languagedesigners,itisworthconsideringsupportforunsignedintegraltypes,whicheliminatethepossibilityofsignextension.Onemightarguethatnegativehexandoctalliteralsshouldbeprohibited,butthiswouldlikelyfrustrateprogrammers,whooftenusehexliteralstorepresentvalueswhosesignisofnosignificance.Puzzle6:MulticastCastsareusedtoconvertavaluefromonetypetoanother.Thisprogramusesthreecastsinsuccession.Whatdoesitprint?publicclassMulticastpublicstaticvoidmain(Stringargs)System.out.println(int)(char)(byte)-1);Solution6:MulticastThisprogramisconfusinganywayyousliceit.Itstartswiththeintvalue-1,thencaststheinttoabyte,thentoachar,andfinallybacktoanint.Thefirstcastnarrowsthevaluefrom32bitsdownto8,thesecondwidensitfrom8bitsto16,andthefinalcastwidensitfrom16bitsbackto32.Doesthevalueendupbackwhereitstarted?Ifyourantheprogram,youfoundthatitdoesnot.Itprints65535,butwhy?Theprogramsbehaviordependscriticallyonthesignextensionbehaviorofcasts.Javausestwos-complementbinaryarithmetic,sotheintvalue-1hasall32bitsset.Thecastfrominttobyteisstraightforward.ItperformsanarrowingprimitiveconversionJLS5.1.3,whichsimplylopsoffallbutthelow-order8bits.Thisleavesabytevaluewithall8bitsset,which(still)represents1.Thecastfrombytetocharistrickierbecausebyteisasignedtypeandcharunsigned.Itisusuallypossibletoconvertfromoneintegraltypetoawideronewhilepreservingnumericalvalue,butitisimpossibletorepresentanegativebytevalueasachar.Therefore,theconversionfrombytetocharisnotconsideredawideningprimitiveconversionJLS5.1.2,butawideningandnarrowingprimitiveconversionJLS5.1.4:Thebyteisconvertedtoanintandtheinttoachar.Allofthismaysoundabitcomplicated.Luckily,thereisasimplerulethatdescribesthesignextensionbehaviorwhenconverting10fromnarrowerintegraltypestowider:Signextensionisperformedifthetypeoftheoriginalvalueissigned;zeroextensionifitisachar,regardlessofthetypetowhichitisbeingconverted.Knowingthisrulemakesiteasytosolvethepuzzle.Becausebyteisasignedtype,signextensionoccurswhenconvertingthebytevalue1toachar.Theresultingcharvaluehasall16bitsset,soitisequalto2161,or65,535.Thecastfromchartointisalsoawideningprimitiveconversion,sotheruletellsusthatzeroextensionisperformedratherthansignextension.Theresultingintvalueis65535,whichisjustwhattheprogramprints.Althoughthereisasimpleruledescribingthesignextensionbehaviorofwideningprimitiveconversionsbetweensignedandunsignedintegraltypes,itisbestnottowriteprogramsthatdependonit.Ifyouaredoingawideningconversiontoorfromachar,whichistheonlyunsignedintegraltype,itisbesttomakeyourintentionsexplicit.Ifyouareconvertingfromacharvaluectoawidertypeandyoudontwantsignextension,considerusingabitmaskforclarity,eventhoughitisntrequired:inti=cAlternatively,writeacommentdescribingthebehavioroftheconversion:inti=c;/SignextensionisnotperformedIfyouareconvertingfromacharvaluectoawiderintegraltypeandyouwantsignextension,castthechartoashort,whichisthesamewidthasacharbutsigned.Giventhesubtletyofthiscode,youshouldalsowriteacomment:inti=(short)c;/CastcausessignextensionIfyouareconvertingfromabytevaluebtoacharandyoudontwantsignextension,youmustuseabitmasktosuppressit.Thisisacommonidiom,sonocommentisnecessary:charc=(char)(bIfyouareconvertingfromabytetoacharandyouwantsignextension,writeacomment:charc=(char)b;/SignextensionisperformedThelessonissimple:Ifyoucanttellwhataprogramdoesbylookingatit,itprobablydoesntdowhatyouwant.Striveforclarity.Althoughasimpleruledescribesthesignextensionbehaviorofwideningconversionsinvolvingsignedandunsignedintegraltypes,mostprogrammersdontknowit.11Ifyourprogramdependsonit,makeyourintentionscler12中文翻译Java谜题1表达式谜题谜题1:奇数性下面的方法意图确定它那唯一的参数是否是一个奇数。这个方法