算法练习——位运算

前言：位运算的方法大多比较抽象，很难想到。

一：判断字符是否唯一

题目要求：

解题思路：

法一：使用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是因为数组中只有两个数，又因为丢失两个数{                                     //所以总和是4tmp ^= 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};}