优选算法——位运算
👇作者其它专栏
1.前要知识
2.相关题解
2.1判定字符是否唯一
算法思路：
利用【位图】的思想，每一个【比特位】代表一个【字符】，一个int类型的变量的32位足够表示所有的小写字母。比特位里若为0，表示这个字符没有出现过；若为1，表示该字符出现过。
可以用一个【整数】来充当【哈希表】。
class Solution { public: bool isUnique(string astr) { //利用鸽巢原理优化 if(astr.size()>26) return false; int bitmap=0; for(auto i:astr){ int e=i-'a'; //先判断字符是否出现过 if(((bitmap>>e)&1)==1) return false; //把当前字符加入到位图中 bitmap|=1<<e; } return true; } };2.2消失的数字
算法思路：
设数组的大小为n，则之前的数组就是[0,n]，数组中是[0,n]中缺失一个数形成的序列。若，我们把数组中的所有数，以及[0,n]中的所有数全部【异或】在一起，那么根据【异或】运算的【消消乐】规则，最终的异或结果就是缺失的数字。
//1.哈希 2.高斯定理 3.位运算 4.排序+（暴力或二分） class Solution { public: int missingNumber(vector<int>& nums) { int ret=0; for(auto i:nums) ret^=i; for(int i=0;i<=nums.size();i++) ret^=i; return ret; } };2.3两整数之和
算法思路：
●异或^运算本质是【无进位加法】；
●按位与&操作能够得到【进位】；
●然后一直循环进行，直到【进位】变成0为止
class Solution { public: int getSum(int a, int b) { while(b){ int x=a^b;//无进位相加的结果 //排除-1的情况 unsigned int carry=(a&b)<<1;//进位 a=x; b=carry; } return a; } };2.4只出现一次的数字 II
算法思路：
设要找的数为ret。由于整个数组中，需要找的元素只出现了【一次】，其余的数都出现了【三次】，因此我们可以根据所有数的【某一个比特位】的总和%3的结果，快速定位到ret的【一个比特位】上的值是0还是1。
这样，我们通过ret的每一位比特位上的值，就可以将ret给还原出来。
class Solution { public: int singleNumber(vector<int>& nums) { int ret=0; for(int i=0;i<32;i++){//依次修改ret中的每一位 int sum=0; for(auto x:nums)//计算nums中所有第i位的和 if(x&(1<<i)) sum++; sum%=3; if(sum&1) ret|=1<<i; } return ret; } };2.5只出现一次的数字 III
算法思路：
1.将所有数异或在一起，由于只有两个数出现一次，其余都出现两次。所以最后的结果为a^b
2.a和b不相等，因此a和b的二进制一定有至少一位不相同，
class Solution { public: vector<int> singleNumber(vector<int>& nums) { //1.将所有的数异或在一起 int tmp=0; for(auto x:nums) tmp^=x; //2.找出a，b中比特位不同的那一位 int diff=0; while(1){ if(((tmp>>diff)&1)==1) break; else diff++; } //3.根据diff位的不同，将所有数划分成两类 int a=0,b=0; for(auto x:nums){ if((1&(x>>diff))==1) b^=x; else a^=x; } return {a,b}; } };2.6消失的两个数字
本题就是 2.2消失的数字+2.5只出现一次的数字 III组合起来的题。
现将数组中的数和[1,n+2]区间内的所有数【异或】在一起，问题就变成了：有两个数出现了【一次】，其余所有的数出现了【两次】。进而变成了2.5只出现一次的数字 III这道题。
class Solution { public: vector<int> missingTwo(vector<int>& nums) { //1.将所有的数异或在一起 int tmp=0; for(auto x:nums) tmp^=x; for(int i=1;i<=nums.size()+2;i++) tmp^=i; //2.找出a，b中比特位不同的那一位 int diff=0; while(1){ if(((tmp>>diff)&1)==1) break; else diff++; } //3.根据diff位的不同，将所有数划分成两类 int a=0,b=0; for(auto x:nums){ if((1&(x>>diff))==1) b^=x; else a^=x; } for(int i=1;i<=nums.size()+2;i++){ if((1&(i>>diff))==1) b^=i; else a^=i; } return {a,b}; } };
