Bitwise Operators in C and C++ - Cprogramming.com

The bitwise AND operator is a single ampersand: &. A handy mnemonic is that the small version of the boolean AND, &&, works on smaller pieces (bits instead of ... BitwiseOperatorsinCandC++ ByAlexAllain Generally,asaprogrammeryoudon'tneedtoconcernyourselfaboutoperations atthebitlevel.You'refreetothinkinbytes,orintsanddoubles,oreven higherleveldatatypescomposedofacombinationofthese.Butthereare timeswhenyou'dliketobeabletogotothelevelofanindividualbit. Exclusive-orencryptionisoneexamplewhenyouneedbitwiseoperations. Anotherexamplecomesupwhendealingwithdatacompression:whatifyou wantedtocompressafile?Inprinciple,thismeanstakingonerepresentation andturningitintoarepresentationthattakeslessspace.Onewayofdoing thisistouseanencodingthattakeslessthan8bitstostoreabyte.(For instance,ifyouknewthatyouwouldonlybeusingthe26lettersoftheRoman alphabetanddidn'tcareaboutcapitalization,you'donlyneed5bitstodo it.)Inordertoencodeanddecodefilescompressedinthismanner,youneed toactuallyextractdataatthebitlevel. Finally,youcanusebitoperationstospeedupyourprogramorperformneat tricks.(Thisisn'talwaysthebestthingtodo.) ThinkingaboutBits Thebyteisthelowestlevelatwhichwecanaccessdata;there'sno"bit"type,andwe can'taskforanindividualbit.Infact,wecan'tevenperformoperationson asinglebit--everybitwiseoperatorwillbeappliedto,ataminimum, anentirebyteatatime.Thismeanswe'llbeconsideringthewhole representationofanumberwheneverwetalkaboutapplyingabitwiseoperator. (Notethatthisdoesn'tmeanwecan'teverchangeonlyonebitatatime;it justmeanswehavetobesmartabouthowwedoit.)Understandingwhatit meanstoapplyabitwiseoperatortoanentirestringofbitsisprobably easiesttoseewiththeshiftingoperators.Byconvention,inCandC++you canthinkaboutbinarynumbersasstartingwiththemostsignificantbitto theleft(i.e.,10000000is128,and00000001is1).Regardlessofunderlying representation,youmaytreatthisastrue.Asaconsequence,theresultsof theleftandrightshiftoperatorsarenotimplementationdependentfor unsignednumbers(forsignednumbers,therightshiftoperatoris implementationdefined). Theleftshiftoperatoristheequivalentofmovingallthebitsofanumbera specifiednumberofplacestotheleft: [variable]<>(especiallyconsideringthatImentioneditearlier).Notethata bitwiseright-shiftwillbetheequivalentofintegerdivisionby2. Whyisitintegerdivision?Considerthenumber5,inbinary,00000101.5/2 is2.5,butifyouareperformingintegerdivision,5/2is2.Whenyou performarightshiftbyone:(unsignedint)5>>1,youendupwith00000010,asthe rightmost1getsshiftedofftheend;thisistherepresentationofthenumber 2.Notethatthisonlyholdstrueforunsignedintegers;otherwise,weare notguaranteedthatthepaddingbitswillbeall0s. Generally,usingtheleftandrightshiftoperatorswillresultin significantlyfastercodethancalculatingandthenmultiplyingbyapowerof two.Theshiftoperatorswillalsobeusefullaterwhenwelookathowto manipulatingindividualbits. Fornow,let'slookatsomeoftheotherbinaryoperatorstoseewhattheycan doforus. BitwiseAND ThebitwiseANDoperatorisasingleampersand:&.Ahandymnemonicis thatthesmallversionofthebooleanAND,&&,worksonsmallerpieces (bitsinsteadofbytes,chars,integers,etc).Inessence,abinaryAND simplytakesthelogicalANDofthebitsineachpositionofanumberin binaryform. Forinstance,workingwithabyte(thechartype): 01001000& 10111000= -------- 00001000 Themostsignificantbitofthefirstnumberis0,soweknowthemost significantbitoftheresultmustbe0;inthesecondmostsignificantbit, thebitofsecondnumberiszero,sowehavethesameresult.Theonlytime wherebothbitsare1,whichistheonlytimetheresultwillbe1,isthe fifthbitfromtheleft.Consequently, 72&184=8 BitwiseOR BitwiseORworksalmostexactlythesamewayasbitwiseAND.Theonly differenceisthatonlyoneofthetwobitsneedstobea1forthat position'sbitintheresulttobe1.(Ifbothbitsarea1,theresultwill alsohavea1inthatposition.)Thesymbolisapipe:|.Again,thisis similartobooleanlogicaloperator,whichis||. 01001000| 10111000= -------- 11111000 andconsequently 72|184=248 Let'stakealookatanexampleofwhenyoucouldusejustthesefour operatorstodosomethingpotentiallyuseful.Let'ssaythatyouwantedto keeptrackofcertainbooleanattributesaboutsomething--forinstance,you mighthaveeightcars(!)andwanttokeeptrackofwhichareinuse.Let's assigneachofthecarsanumberfrom0to7. Sincewehaveeightitems,allwereallyneedisasinglebyte,andwe'lluse eachofitseightbitstoindicatewhetherornotacarisinuse.Todo this,we'lldeclareacharcalledin_use,andsetittozero.(We'llassume thatnoneofthecarsareinitially"inuse".) charin_use=0; Now,howcanwechecktomakesurethataparticularcarisfreebeforewetry touseit?Well,weneedtoisolatetheonebitthatcorrespondstothatcar. Thestrategyissimple:usebitwiseoperatorstoensureeverybitofthe resultiszeroexcept,possibly,forthebitwewanttoextract. Considertryingtoextractthefifthbitfromtherightofanumber:XX?XXXXX Wewanttoknowwhatthequestionmarkis,andwearen'tconcernedaboutthe Xs.We'dliketobesurethattheXbitsdon'tinterferewithourresult,so weprobablyneedtouseabitwiseANDofsomekindtomakesuretheyareall zeros.Whataboutthequestionmark?Ifit'sa1,andwetakethebitwise ANDofXX?XXXXXand00100000,thentheresultwillbe00100000: XX1XXXXX& 00100000= -------- 00100000 Whereas,ifit'sazero,thentheresultwillbe00000000: XX0XXXXX& 00100000= -------- 00000000 Sowegetanon-zeronumberif,andonlyif,thebitwe'reinterestedinisa 1. Thisprocedureworksforfindingthebitinthenthposition.Theonlything lefttodoistocreateanumberwithonlytheonebitinthecorrectposition turnedon.Thesearejustpowersoftwo,sooneapproachmightbetodo somethinglike: intis_in_use(intcar_num) { //powreturnsanint,butin_usewillalsobepromotedtoanint //soitdoesn'thaveanyeffect;wecanthinkofthisasanoperation //betweenchars returnin_use&pow(2,car_num); } Whilethisfunctionworks,itcanbeconfusing.Itobscuresthefactthat whatwewanttodoisshiftabitoveracertainnumberofplaces,sothatwe haveanumberlike00100000--acoupleofzeros,aone,andsomemorezeros. (Theonecouldalsobefirstorlast--10000000or00000001.) Wecanuseabitwiseleftshifttoaccomplishthis,andit'llbemuchfasterto boot.Ifwestartwiththenumber1,weareguaranteedtohaveonlyasingle bit,andweknowit'stothefar-right.We'llkeepinmindthatcar0will haveitsdatastoredintherightmostbit,andcar7willbetheleftmost. intis_in_use(intcar_num) { returnin_use&1<>shift_arg Shiftsbitstoofbit_argshift_argplacestotheright--equivalentto integerdivisionby2^shift_arg Worksonthebitsofbotharguments left_arg&right_arg TakesthebitwiseANDofleft_argandright_arg left_arg^right_arg TakesthebitwiseXORofleft_argandright_arg left_arg|right_arg Worksonthebitsofonlyargument ~arg Reversesthebitsofarg Skillsandknowledge Youalsoknowacoupleofneattricksthatyoucanusewhenperformanceis critical,orspaceisslow,oryoujustneedtoisolateandmanipulate individualbitsofanumber. Andyounowshouldhaveabettersenseofwhatgoesonatthelowestlevels ofyourcomputer. APartingPuzzle Onefinalneattrickofbitwiseoperatorsisthatyoucanusethem,in conjunctionwithabitofmath,tofindoutwhetheranintegerisapoweroftwo. Takesometimetothinkaboutit,thencheckoutthesolution. RelatedarticlesAbitofbackgroundinbitsandafewothertricks Popularpages JumpingintoC++,theCprogramming.comebook HowtolearnC++orC CTutorial C++Tutorial 5waysyoucanlearntoprogramfaster The5mostcommonproblemsnewprogrammersface Howtosetupacompiler Howtomakeagamein48hours Advertising|Privacypolicy| Copyright©2019Cprogramming.com|Contact|About