目录1.基础位运算的知识1.1给定一个数字n确定二进制第x位是1还是01.2将一个二进制数的第x位变成1或者01.3位图1.4提取一个数最右侧的11.5去掉最低位的11.6亦或的运算律2.位运算习题2.1判定字符是否唯一2.2丢失的数字2.3两整数之和2.4只出现一次的数字II2.5消失的两个数字1.基础位运算的知识左移整体向左移动一位右侧补0右移整体向右移动一位左侧正数补0负数补1~按位取反按位与有0则0|按位或有1则1^亦或可以理解为相同为0不同为1或者不进位相加按照8位二进制的数字来简单讲解一下上面知识例如现在有两个数字100000 1010 /270001 101110左移一位结果是0001 010010右移一位结果是0000 0101将10按位取反结果是1111 010110和27按位与结果是0000 101010和27按位或结果是0001 101110和27亦或结果是0001 0001这一块并不难写几个数字练习一下就行1.1给定一个数字n确定二进制第x位是1还是0例如一个二进制数00101101想确定第3位是1还是0可以将n右移x位然后和1进行按位与注意这里我们从右侧开始计算位数并且是从第0位开始计算因为这样想知道第几位向右移动几位即可因为1除了最后一位都是0将n右移x位相当于将第x位移动到最后一个位置最终按位与的结果只和第x位相关所以这样可以确定第x位是0还是11.2将一个二进制数的第x位变成1或者0例如这个数0011 0011想将第二位修改成1只需将1左移两位让0000 0100和原数进行按位或即可因为按位或有1则1所以这样做只会对第x位进行修改类似的方法想将第一位修改成0也非常简单只需将1移动一位然后按位取反最后的结果和原数进行按位与即可这样可以保证其他位不变的同时只让第x位和0进行一个按位或修改成01.3位图比如一个长度为5的数组可以用每一位存储信息但是我们也可以不用数组只用一个数字的每一位的01变换去存储信息比如00000000 00000000 00000000 00000000一个数字有32位32位环境每一位是1或者0可以存储对应的一种信息这样可以节省空间1.4提取一个数最右侧的1先说结果例如一个数字n最终结果是n(-n)也就是n和-n按位与即可例如一个正数n他的最右侧的1在第x位将n取反之后根据补码的知识负数补码是除了符号位之外按位取反1那么就可以让n和-n只有第x位是相同的举一个具体例子0100 1000这里为了方便采用八位有符号二进制先是负数原码1100 1000补码为1011 01110000 0001也就是1011 1000因为第x位是最低的1所以第x位右侧本来全是0进行按位取反之后第x位变成0右侧全部变成1此时再加1右侧全部进位最终使得第x位还是1并且右侧依旧全是0至于第x位左侧全部取反之外没有其他变化所以我们发现将n和-n进行按位与之后第x位左侧和右侧都会变成0只留下第x位的1这样就取出了最低位的1也就是0000 1000注意这里提取1的含义是二进制表示下只有一个1并不是数值为11.5去掉最低位的1因为最低位的1在减一之后右侧的0会全部变成1而自己变成0其他位保持不变所以只需要n(n-1)即可去掉最低位的11.6亦或的运算律a^a00^aaa^b^ca^(b^c)注意亦或可以满足交换律因为可以每一位的不进位相加所以可以看作加法满足交换律2.位运算习题2.1判定字符是否唯一面试题 01.01. 判定字符是否唯一 - 力扣LeetCode这道题很明显可以用哈希表的方式每次有新元素就丢进哈希表判断是否有重复即可但是我们也可以用位图的思想因为输入只有小写字母最多就26种情况而int可以有32位的比特位所以利用位图即可快速实现和哈希表一样的功能当某个字母对应的位置为0说明还没有该字母如果为1说明已经有这个字母了逻辑也非常简单根据字母的ascii码表每个字母和a之间的距离作为在位图的位置遍历到某个字母将该位置设为1即可代码部分每次遍历到新位置就判断该字母对应的位置是否已经是1了如果是0就将该位置设为1如果是1说明重复了那么返回falseclass Solution { public: bool isUnique(string astr) { int ret0; for(auto e:astr){ int lene-a; if((retlen)1)return false; else ret|(1len); } return true; } };2.2丢失的数字268. 丢失的数字 - 力扣LeetCode这是一个乱序的数组所以不能用二分来解但是我们学过亦或的计算让0依次亦或给定数组和给定数组补全后的数组进行两次循环亦或我们可以得出两次循环亦或完剩下的结果就是丢失的数字也许有点抽象我们举个例子比如示例1数组【301】完整的数组应该是【0123】因为亦或满足交换律所以对应完整的数组我们直接当作有序也没问题已知a^a0也就是相同的数字亦或之后相当于消除了0^aa也就是和0亦或不影响数字本身所以1和13和30和0都已经亦或之后变成了0最后就是0^2结果是2所以亦或的最终结果就是丢失的那个数字因为它没有相同数字进行亦或仍然存在代码部分class Solution { public: int missingNumber(vectorint nums) { int ret0; for(int i0;inums.size();i){ ret^i; } for(auto e:nums){ ret^e; } return ret; } };2.3两整数之和371. 两整数之和 - 力扣LeetCode这道题就需要应用亦或等价于无进位相加的思想来解因为亦或相当于无进位的一次相加那么只需要将需要进位的那些位置找到补足进位即可注意到只有两个数字均为1的时候会丢失一个进位所以使用一次按位与即可找到原本需要向前进位的位置然后将结果向左移一位并和亦或完的结果再次亦或相当于把进位补上但是有可能又遇到11亦或的情况所以要反复这个过程直到没有需要进位的操作代码部分class Solution { public: int getSum(int a, int b) { //亦或相当于进行不进位相加 //按位与相当于找到进位的位置然后左移一位是需要1的位置 //所以亦或完的结果和按位与移动结果再次亦或 //相当于把缺少的进位补上 //直到不需要进位 while(b){ int xa^b; b(ab)1; ax; } return a; } };2.4只出现一次的数字II137. 只出现一次的数字 II - 力扣LeetCode对于除了目标元素以外的数字均出现了三次也就是说对于二进制的第x位如果目标数字是0该位置上的数字的累加和一定是3的倍数因为其他数字如果该位置是1一定会有三次1加上去最极端也就是该位置不存在数字0是3的0倍也是合理的而如果目标数字在该位置是1最终结果肯定是3n1(n根据情况而定)所以我们只需要依次统计每一个位置数字的累计和然后%3就是最后的结果如果目标数字在该位置是0那么3n%30如果位1那么3n1%31就可以去除掉其他数据的干扰最终得到只出现一次的数字代码部分class Solution { public: int singleNumber(vectorint nums) { int sum0; int ret0; for(int i0;i32;i){ ret0; for(auto e:nums){ ret(ei)1; } ret%3; sum|(reti); } return sum; } };2.5消失的两个数字面试题 17.19. 消失的两个数字 - 力扣LeetCode这道题同样可以使用亦或的方法进行解题根据刚才第二题的经验我们想到了将所有数字进行亦或也就是亦或丢失数组和完整数组最终会得到一个数字但是这个数字是丢失的两个数字亦或的结果注意这两个数字因为不可能重复所以至少有一位不同也就是亦或结果的二进制表示至少存在一个1这个1就表示在该位置这两个数字一个是0一个是1那么我们就通过最低位的1来进行分类将所有数据分为两类一类是该位置为0的数字一类是该位置为1的数字那么我们可以走两路亦或相当于是把两个数字拆开放到两个数组里做两次丢失的数字即可代码部分lowbit就是最低位1的一个分类标准根据该数字和lowbit按位与的结果判断该位置是1还是0进行分别的亦或最终就可以得到两组亦或的结果就是消失的两个数字class Solution { public: vectorint missingTwo(vectorint nums) { int ret0; for(int i1;inums.size()2;i){ ret^i; } for(auto e:nums){ ret^e; } int lowbitret(-ret); int a0; int b0; for(auto e:nums){ if(elowbit)a^e; else b^e; } for(int i1;inums.size()2;i){ if(ilowbit)a^i; else b^i; } return {a,b}; } };