Findingintegerlogbase2ofaninteger（akathepositionofthehighestbitset）
●Findthelogbase2ofanintegerwiththeMSBNsetinO（N）operations（theobviousway）
●Findtheintegerlogbase2ofanintegerwithan64-bitIEEEfloat
●Findthelogbase2ofanintegerwithalookuptable
●Findthelogbase2ofanN-bitintegerinO（lg（N））operations
●Findthelogbase2ofanN-bitintegerinO（lg（N））operationswithmultiplyandlookup
Findintegerlogbase10ofaninteger
Findintegerlogbase10ofanintegertheobviousway
Findintegerlogbase2ofa32-bitIEEEfloat
Findintegerlogbase2ofthepow（2,r）-rootofa32-bitIEEEfloat（forunsignedintegerr）
Countingconsecutivetrailingzerobits（orfindingbitindices）
●Counttheconsecutivezerobits（trailing）ontherightlinearly
●Counttheconsecutivezerobits（trailing）ontherightinparallel
●Counttheconsecutivezerobits（trailing）ontherightbybinarysearch
●Counttheconsecutivezerobits（trailing）ontherightbycastingtoafloat
●Counttheconsecutivezerobits（trailing）ontherightwithmodulusdivisionandlookup
●Counttheconsecutivezerobits（trailing）ontherightwithmultiplyandlookup
Rounduptothenexthighestpowerof2byfloatcasting
Rounduptothenexthighestpowerof2
Interleavingbits（akacomputingMortonNumbers）
●Interleavebitstheobviousway
●Interleavebitsbytablelookup
●Interleavebitswith64-bitmultiply
●InterleavebitsbyBinaryMagicNumbers
Testingforrangesofbytesinaword（andcountingoccurancesfound）
●Determineifawordhasazerobyte
●Determineifawordhasabyteequalton
●Determineifawordhasbytelessthann
●Determineifawordhasabytegreaterthann
●Determineifawordhasabytebetweenmandn
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）;//trueifxandyhaveoppositesigns
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,YuriyKaminskiytoldmethatthepatentislikelyinvalidbecausethemethodwaspub
升级会员 