C语言位操作艺术.docx
- 文档编号:12826432
- 上传时间:2023-06-08
- 格式:DOCX
- 页数:58
- 大小:43.95KB
C语言位操作艺术.docx
《C语言位操作艺术.docx》由会员分享,可在线阅读,更多相关《C语言位操作艺术.docx(58页珍藏版)》请在冰点文库上搜索。
C语言位操作艺术
BitTwiddlingHacks
BySeanEronAnderson
seander@cs.stanford.edu
Individually,thecodesnippetshereareinthepublicdomain(unlessotherwisenoted)—feelfreetousethemhoweveryouplease.Theaggregatecollectionanddescriptionsare©1997-2005SeanEronAnderson.Thecodeanddescriptionsaredistributedinthehopethattheywillbeuseful,butWITHOUTANYWARRANTYandwithouteventheimpliedwarrantyofmerchantabilityorfitnessforaparticularpurpose.AsofMay5,2005,allthecodehasbeentestedthoroughly.Thousandsofpeoplehavereadit.Moreover,ProfessorRandalBryant,theDeanofComputerScienceatCarnegieMellonUniversity,haspersonallytestedalmosteverythingwithhisUclidcodeverificationsystem.Whathehasn'ttested,Ihavecheckedagainstallpossibleinputsona32-bitmachine.Tothefirstpersontoinformmeofalegitimatebuginthecode,I'llpayabountyofUS$10(bycheckorPaypal).Ifdirectedtoacharity,I'llpayUS$20.
Contents
∙Abouttheoperationcountingmethodology
∙Computethesignofaninteger
∙Detectiftwointegershaveoppositesigns
∙Computetheintegerabsolutevalue(abs)withoutbranching
∙Computetheminimum(min)ormaximum(max)oftwointegerswithoutbranching
∙Determiningifanintegerisapowerof2
∙Signextending
oSignextendingfromaconstantbit-width
oSignextendingfromavariablebit-width
oSignextendingfromavariablebit-widthin3operations
∙Conditionallysetorclearbitswithoutbranching
∙Conditionallynegateavaluewithoutbranching
∙Mergebitsfromtwovaluesaccordingtoamask
∙Countingbitsset
oCountingbitsset,naiveway
oCountingbitssetbylookuptable
oCountingbitsset,BrianKernighan'sway
oCountingbitssetin14,24,or32-bitwordsusing64-bitinstructions
oCountingbitsset,inparallel
oCountbitsset(rank)fromthemost-significantbituptoagivenposition
oSelectthebitposition(fromthemost-significantbit)withthegivencount(rank)
∙Computingparity(1ifanoddnumberofbitsset,0otherwise)
oComputeparityofawordthenaiveway
oComputeparitybylookuptable
oComputeparityofabyteusing64-bitmultiplyandmodulusdivision
oComputeparityofwordwithamultiply
oComputeparityinparallel
∙SwappingValues
oSwappingvalueswithsubtractionandaddition
oSwappingvalueswithXOR
oSwappingindividualbitswithXOR
∙Reversingbitsequences
oReversebitstheobviousway
oReversebitsinwordbylookuptable
oReversethebitsinabytewith3operations(64-bitmultiplyandmodulusdivision)
oReversethebitsinabytewith4operations(64-bitmultiply,nodivision)
oReversethebitsinabytewith7operations(no64-bit,only32)
oReverseanN-bitquantityinparallelwith5*lg(N)operations
∙Modulusdivision(akacomputingremainders)
oComputingmodulusdivisionby1< oComputingmodulusdivisionby(1< oComputingmodulusdivisionby(1< ∙Findingintegerlogbase2ofaninteger(akathepositionofthehighestbitset) oFindthelogbase2ofanintegerwiththeMSBNsetinO(N)operations(theobviousway) oFindtheintegerlogbase2ofanintegerwithan64-bitIEEEfloat oFindthelogbase2ofanintegerwithalookuptable oFindthelogbase2ofanN-bitintegerinO(lg(N))operations oFindthelogbase2ofanN-bitintegerinO(lg(N))operationswithmultiplyandlookup ∙Findintegerlogbase10ofaninteger ∙Findintegerlogbase10ofanintegertheobviousway ∙Findintegerlogbase2ofa32-bitIEEEfloat ∙Findintegerlogbase2ofthepow(2,r)-rootofa32-bitIEEEfloat(forunsignedintegerr) ∙Countingconsecutivetrailingzerobits(orfindingbitindices) oCounttheconsecutivezerobits(trailing)ontherightlinearly oCounttheconsecutivezerobits(trailing)ontherightinparallel oCounttheconsecutivezerobits(trailing)ontherightbybinarysearch oCounttheconsecutivezerobits(trailing)ontherightbycastingtoafloat oCounttheconsecutivezerobits(trailing)ontherightwithmodulusdivisionandlookup oCounttheconsecutivezerobits(trailing)ontherightwithmultiplyandlookup ∙Rounduptothenexthighestpowerof2byfloatcasting ∙Rounduptothenexthighestpowerof2 ∙Interleavingbits(akacomputingMortonNumbers) oInterleavebitstheobviousway oInterleavebitsbytablelookup oInterleavebitswith64-bitmultiply oInterleavebitsbyBinaryMagicNumbers ∙Testingforrangesofbytesinaword(andcountingoccurancesfound) oDetermineifawordhasazerobyte oDetermineifawordhasabyteequalton oDetermineifawordhasbytelessthann oDetermineifawordhasabytegreaterthann oDetermineifawordhasabytebetweenmandn ∙Computethelexicographicallynextbitpermutation Abouttheoperationcountingmethodology Whentotalingthenumberofoperationsforalgorithmshere,anyCoperatoriscountedasoneoperation.Intermediateassignments,whichneednotbewrittentoRAM,arenotcounted.Ofcourse,thisoperationcountingapproachonlyservesasanapproximationoftheactualnumberofmachineinstructionsandCPUtime.Alloperationsareassumedtotakethesameamountoftime,whichisnottrueinreality,butCPUshavebeenheadingincreasinglyinthisdirectionovertime.Therearemanynuancesthatdeterminehowfastasystemwillrunagivensampleofcode,suchascachesizes,memorybandwidths,instructionsets,etc.Intheend,benchmarkingisthebestwaytodeterminewhetheronemethodisreallyfasterthananother,soconsiderthetechniquesbelowaspossibilitiestotestonyourtargetarchitecture. Computethesignofaninteger intv;//wewanttofindthesignofv intsign;//theresultgoeshere //CHAR_BITisthenumberofbitsperbyte(normally8). sign=-(v<0);//ifv<0then-1,else0. //or,toavoidbranchingonCPUswithflagregisters(IA32): sign=-(int)((unsignedint)((int)v)>>(sizeof(int)*CHAR_BIT-1)); //or,foronelessinstruction(butnotportable): sign=v>>(sizeof(int)*CHAR_BIT-1); Thelastexpressionaboveevaluatestosign=v>>31for32-bitintegers.Thisisoneoperationfasterthantheobviousway,sign=-(v<0).Thistrickworksbecausewhensignedintegersareshiftedright,thevalueofthefarleftbitiscopiedtotheotherbits.Thefarleftbitis1whenthevalueisnegativeand0otherwise;all1bitsgives-1.Unfortunately,thisbehaviorisarchitecture-specific. Alternatively,ifyouprefertheresultbeeither-1or+1,thenuse: sign=+1|(v>>(sizeof(int)*CHAR_BIT-1));//ifv<0then-1,else+1 Ontheotherhand,ifyouprefertheresultbeeither-1,0,or+1,thenuse: sign=(v! =0)|-(int)((unsignedint)((int)v)>>(sizeof(int)*CHAR_BIT-1)); //Or,formorespeedbutlessportability: sign=(v! =0)|(v>>(sizeof(int)*CHAR_BIT-1));//-1,0,or+1 //Or,forportability,brevity,and(perhaps)speed: sign=(v>0)-(v<0);//-1,0,or+1 Ifinsteadyouwanttoknowifsomethingisnon-negative,resultingin+1orelse0,thenuse: sign=1^((unsignedint)v>>(sizeof(int)*CHAR_BIT-1));//ifv<0then0,else1 Caveat: OnMarch7,2003,AngusDugganpointedoutthatthe1989ANSICspecificationleavestheresultofsignedright-shiftimplementation-defined,soonsomesystemsthishackmightnotwork.Forgreaterportability,TobySpeightsuggestedonSeptember28,2005thatCHAR_BITbeusedhereandthroughoutratherthanassumingbyteswere8bitslong.Angusrecommendedthemoreportableversionsabove,involvingcastingonMarch4,2006.RohitGargsuggestedtheversionfornon-negativeintegersonSeptember12,2009. Detectiftwointegershaveoppositesigns intx,y;//inputvaluestocomparesigns boolf=((x^y)<0);//trueiffxandyhaveoppositesigns ManfredWeissuggestedIaddthisentryonNovember26,2009. Computetheintegerabsolutevalue(abs)withoutbranching intv;//wewanttofindtheabsolutevalueofv unsignedintr;//theresultgoeshere intconstmask=v>>sizeof(int)*CHAR_BIT-1; r=(v+mask)^mask; Patentedvariation: r=(v^mask)-mask; SomeCPUsdon'thaveanintegerabsolutevalueinstruction(orthecompilerfailstousethem).Onmachineswherebranchingisexpensive,theaboveexpressioncanbefasterthantheobviousapproach,r=(v<0)? -(unsigned)v: v,eventhoughthenumberofoperationsisthesame. OnMarch7,2003,AngusDugganpointedoutthatthe1989ANSICspecificationleavestheresultofsignedright-shiftimplementation-defined,soonsomesystemsthishackmightnotwork.I'vereadthatANSICdoesnotrequirevaluestoberepresentedastwo'scomplement,soitmaynotworkforthatreasonaswell(onadiminishinglysmallnumberofoldmachinesthatstilluseone'scomplement).OnMarch14,2004,KeithH.Duggarsentmethepatentedvariationabove;itissuperiortotheoneIinitiallycameupwith,r=(+1|(v>>(sizeof(int)*CHAR_BIT-1)))*v,becauseamultiplyisnotused.Unfortunately,thismethodhasbeenpatentedintheUSAonJune6,2000byVladimirYuVolkonskyandassignedtoSunMicrosystems.OnAugust13,2006,YuriyKaminskiytoldmethatthepatentislikelyinvalidbecausethemethodwaspublishedwellbeforethepatentwasevenfiled,suchasinHowtoOptimizeforthePentiumProcessorbyAgnerFog,datedNovember,9,1996.YuriyalsomentionedthatthisdocumentwastranslatedtoRussianin1997,whichVladimircouldhaveread.Moreover,theInternetArchivealsohasa
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 语言 操作 艺术