位运算1.常见位运算总结常见的位运算有左移、右移、按位取反~、按位与、按位或|、异或^。使用位运算尽量加括号以明确优先级。给二进制数的每一位从右往左从0开始编号。给一个数n确定它的二进制表示中的第x位是0还是1。先把n右移x位把第x位变成最低位再按位与1即(nx)1。1的二进制是00000001如果第x位是0则结果为0如果第x位是1则结果为1。将一个数n的二进制表示的第x位修改成1。n n|(1x)即n | (1x)。1左移x位到指定位使得1x的第x位是1第x位左右两侧都是0此时n按位或上1x就会使n的第x位变成1而其它位不变。将一个数n的二进制表示的第x位修改成0。n n(~(1x))即n (~(1x))。提取一个数n二进制表示中最右侧的1最低位的1。n (-n)。由n按位取反再1得 -n。去掉一个数n二进制表示中最右侧的1。n (n-1)。n-1会使n的最低位的1变为0其右侧的每一位0都变为1。异或的运算律异或相同为0相异为1。异或等价于二进制无进位加法即0101为00其中11不进位。a^a0、a^0a、交换律a^b b^a、结合律(a^b)^c a^(b^c)。消去律若a^b a^c则bc。位图一个int类型的变量有32 bit位每个bit位为0或1可以借助每个bit位来表示某种信息类似哈希表但是比哈希表更节省空间。2.判断字符是否唯一如果astr的长度大于26由鸽巢原理一定有重复字符返回false。创建一个int变量bitmap建立字符与bit位的映射如果字符出现了bitmap对应的bit位变为1如果字符重复出现bitmap对应的bit位就是1。classSolution{public:boolisUnique(string astr){if(astr.size()26)returnfalse;//位图intbitmap0;for(autoch:astr){intich-a;//字符与bit位的映射if(((bitmapi)1)1)//判断字符是否出现过returnfalse;bitmap|(1i);//当前字符加入位图}returntrue;}};3.丢失的数字根据异或的性质a^a0、a^0a以及异或满足交换律和结合律。classSolution{public:intmissingNumber(vectorintnums){intret0;for(autoe:nums)ret^e;for(inti0;inums.size();i)ret^i;returnret;}};4.两整数之和异或等价于二进制无进位加法可以考虑用异或解决。例如13284113的二进制00110128的二进制01110041的二进制101001。令a13b28a^b 010001ab 101001显然a^b是没有进位的。只有11才需要进位1其余进位0这就类似所以通过(ab)1算出进位。把 a^b当成新的a(ab)1当成新的b不断循环当进位为0时就得到ab。快速求二进制。从右往左列12481632……每个数下面为0配凑1313841对应数字下面记为1此时数字序列即为13的二进制。classSolution5{public:intgetSum(inta,intb){while(b!0){intxa^b;//无进位相加的结果unsignedinty(unsignedint)(ab)1;//算出进位ax;by;}returna;}};5.只出现一次的数字nums中每个元素的每个bit位要么是0要么是1nums的元素个数为n只出现一次的元素为a。nums中所有元素的某个bit位的和只能有4种情况3n个0 0 03n个0 1 13n个1 0 3n3n个1 1 3n1。这些和模3的结果为0、1、0、1即结果为0则只出现一次的元素a对应的bit位是0结果为1a对应的bit位是1。由此能得到a的所有bit位进而得到a。题目可扩展为某个元素只出现1次其余每个元素恰出现n次。此时对应模n即可。classSolution{public:intsingleNumber(vectorintnums){intret0;for(inti0;i32;i)//遍历nums每个元素的每一个bit位{intsum0;for(autoe:nums)// 计算nums中所有数的第 i 位的和if(((ei)1)1)sum;sum%3;if(sum1)ret|(1i);}returnret;}};6.消失的两个数字根据题意1~N与nums相比1 ~N其余与nums一样只多了两个数ab要求返回ab。把1 ~N和nums的所有数异或得到t即ta^b。t中bit位为1的那一位说明a和b在该位上是不同的我们选t的最低位的1在所有数中在该位为0的数分在一起在该位为1的数分在一起这样就分开了ab。相同的数也会分在一起比如nums中的1和1 ~N中的1会分在一起nums中的2和1 ~N中的2会一起分到另一部分分别异或这两部分数字即可得到ab。classSolution{public:vectorintmissingTwo(vectorintnums){//将所有数异或在一起intt0;for(autoe:nums)t^e;for(inti1;inums.size()2;i)t^i;//找出 ab 中bit位不同的那一位intdiff0;while(1){if(((tdiff)1)1)break;elsediff;}//根据 diff 位的不同将所有的数划分为两类来异或inta0,b0;for(autoe:nums)if(((ediff)1)1)a^e;elseb^e;for(inti1;inums.size()2;i)if(((idiff)1)1)a^i;elseb^i;return{a,b};}};