算法优选：位运算技巧

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};
    }
};