【算法】位运算
个人主页 ： zxctscl 如有转载请先通知
1. 面试题 01.01. 判定字符是否唯一
1.2 分析
这里题目中所给了限制条件表示，只有小写的字母，就有26个。 就可以创建一个int位图，让26个小写字母映射到位图中，0表示没有出现过，1表示出现过。 利用右移操作符将不同字母的位图按位与上1，如果等于1，那么这个字母就出现过，如果没有出现过就把这个位置异或上1，再左移回去。 如果给的字符串长度超过26那么肯定会有重复的字母。
1.2 代码
class Solution {
public:
bool isUnique(string astr) {
if(astr.size()>26)return false;
int bitMap=0;
for(auto ch:astr)
{
int i=ch-'a';
if(((bitMap>>i)&1)==1)return false;
bitMap|=1<<i;
}
return true;
}
};2. 268. 丢失的数字
2.1 分析
这里就用异或来做。 异或有一个性质，自己异或自己等于0。 那么就让数组异或上从0到size()，最后返回的值就是没有的那个值。
2.2 代码
class Solution {
public:
int missingNumber(vector<int>& nums) {
int ret=0;
for(auto e:nums)ret^=e;
for(int i=0;i<=nums.size();i++)ret^=i;
return ret;
}
};3. 371. 两整数之和
3.1 分析
用到异或运算，它有个特点：无进位相加。然后再利用按位与找到进位左移一位。继续把异或结果和进位位置在无进位相加在进位，一直重复，直到进位变成0，最后的无进位相加就是结果。
3.2 代码
class Solution {
public:
int getSum(int a, int b) {
while(b!=0)
{
int x=a^b;
unsigned y=(a&b)<<1;
a=x;b=y;
}
return a;
}
};4. 137. 只出现一次的数字 II
4.1 分析
把这些元素按32位位图存起来，重复3次的数位图的最后一位是0或者1，出现一次的数位图最后一位也是0或者1，它们这个位图这个位置的和就是0、1、3n、3n+1。此时把这些数都模上3，最后出现的结果和出现一次a的正好对应。把所以数的所以对应位置位图都加起来，在模上3，就得到出现一次数那个位置得位图是0还是1，是0就修改为0，是1就修改为1，然后以此类推，把这32个比特位全部修改完毕。
4.2 代码
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret=0;
for(int i=0;i<32;i++)
{
int sum=0;
for(int x:nums)
if(((x>>i)&1)==1)sum++;
sum%=3;
if(sum==1)ret|=1<<i;
}
return ret;
}
};5. 面试题 17.19. 消失的两个数字
5.1 分析
一、题目分析 给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。就说明这个数组其实总的长度是N+2。
二、算法原理 使用位运算。 就像前面消失的数字一样，可以先做异或操作把消失的两个数字先取出来。 因为两个数字是不相同的，那么它们的二进制位置上遇到有个位置是1，就可以将数据分为两部分，一部分是位置是1的，一部分不是。 将取出来的数字在分别和这两种情况下再按位异或，就可以得到这两个值。
5.2 代码
class Solution {
public:
vector<int> missingTwo(vector<int>& nums) {
int tmp=0;
for(auto x:nums)tmp^=x;
for(int i=1;i<=nums.size()+2;i++)tmp^=i;
int diff=0;
while(1)
{
if(((tmp>>diff)&1)==1)break;
else diff++;
}
int a=0,b=0;
for(auto x:nums)
{ if(((x>>diff)&1)==1)b^=x;
else a^=x;
}
for(int i=1;i<=nums.size()+2;i++)
{
if(((i>>diff)&1)==1)b^=i;
else a^=i;
}
return {a,b};
}
};有问题请指出，大家一起进步！！！
腾讯云开发者
