算法练习——位运算
前言：位运算的方法大多比较抽象，很难想到。
一：判断字符是否唯一
题目要求：
解题思路：
法一：使用hash的思想，统计每一个字母出现的次数，再通过一次循环遍历查询是否有超过1的字母，有就返回false，没有返回true
法二：位运算(此处利用位图的思想)。字母一共只有26个，而一个int型整数有32个bit位，因此完全能够通过一个 int型整数的不同位 来充当hash表来统计每个字母出现的次数，想法和法一类似，只不过是通过位图的思想来实现
实现代码：
bool isUnique(string astr) {
int Bit_Count = 0;
for(auto s : astr)
{
if(((Bit_Count >> (s-'a')) & 1) == 1)
{
return false;
}
else{
Bit_Count |=(1<<s-'a');
}
}
return true;
}二：丢失的数字
题目要求：
解题思路：
后续表达中：将丢失的数字 = 答案
思路：先将所有的数据异或，然后再将异或得到的结果与 0~n的所有数异或，最终得到答案。
之所以能够得到答案是因为，这两组数中，只有答案出现了一次，其他均出现了两次，而 a ^ a = 0，0 ^ b = b。
实现代码：
int missingNumber(vector<int>& nums) {
int n = nums.size();
int tmp = 0;
for(auto num : nums)
{
tmp ^= num;
}
while(n)
{
tmp^=n;
n--;
}
return tmp;
}三：两整数之和
题目要求：
解题思路：
实现代码：
int getSum(int a, int b) {
while(b)
{
int c = a;
a ^= b;
b &= c;
b<<=1;
}
return a^b;
}四：只出现一次的数字Ⅱ
题目要求：
解题思路：
后续表达中：将丢失的数字 = 答案
思路：数组的规律是：一个数出现3次，另一个数出现1次。那么就按bit位，通过for循环，记录32个bit位上，统计每位1出现的次数。
如果某位统计得到的1的个数为 0或3，说明该位不是答案的高位之一
如果某位统计得到的1的个数为 1或4，说明该位是答案的高位之一
补：按照上述思路，可以写出任意一个出现n次的数和出现1次的数的代码。
实现代码：
int singleNumber(vector<int>& nums) {
int dest = 0;
for(int i = 0; i<32; i++)
{
int total = 0;
for(auto s : nums)
{
//统计每一位上1出现的次数
if(((s>>i) & 1) == 1)
{
total++;
}
}
//若出现的次数%3 不为0 说明最终答案在该位上为高位
if(total%3 == 1)
{
dest |= (1<<i);
}
}
return dest;
}五：只出现一次的数字Ⅲ
题目要求：
解题思路：
思路：以示例1为例，将所有数异或得到 3^5。再去查找 3^5 中 第一个1的位置diff，并记录下来，diff位上，3和5是的位数是不同的。然后我们再一次去异或这组数据，不过需要以diff位上是否为高位作为条件去异或，这样异或就把 3 5 拆分开来了，并最终得到答案。
实现代码：
vector<int> singleNumber(vector<int>& nums) {
int tmp = 0;
//第一次异或得到 两个数的异或值
for(auto s : nums)
{
tmp ^= s;
}
int diff = 0;
//循环找1，分了将两个数分开
while(1)
{
if(((tmp>>diff) & 1) == 1)
{
break;
}
diff++;
}
//再次异或得到答案
int a = 0;
int b = 0;
for(auto s : nums)
{
if(((s>>diff) & 1) == 1)
{
a^=s;
}
else
{
b^=s;
}
}
return {a,b};
}六：消失的两个数字
题目要求：
解题思路：
后续表达中：将丢失的数字 = 答案1、答案2
此题结合了第二题与第五题的思路
思路：我们先按照第二题的思路，将所有数异或，因为数组包含1~N所有整数，所有我们再异或这1~N的所有整数，这样就得到了：答案1 ^ 答案2，此时这题就变成了第五题的样子，接下来的思路就和第五题完全一样了。
实现代码：
vector<int> missingTwo(vector<int>& nums) {
int tmp = 0;
for(auto s : nums)
{
tmp ^= s;
}
for(int i = 1; i<=nums.size()+2; i++) //+2是因为数组中只有两个数，又因为丢失两个数
{ //所以总和是4
tmp ^= i;
}
int diff = 0;
while(1)
{
if((tmp>>diff) & 1) break;
diff++;
}
int a = 0;
int b = 0;
for(auto s : nums)
{
if(((s>>diff) & 1) == 1)
{
a^=s;
}
else
{
b^=s;
}
}
for(int i = 1; i<=nums.size()+2; i++)
{
if(((i>>diff) & 1) == 1)
{
a^=i;
}
else
{
b^=i;
}
}
return {a,b};
}