算法优选技巧：位运算实战解析

两整数之和

思路分析： ● 异或 ^ 运算本质是【无进位加法】； ● 按位与 & 操作能够得到【进位】； ● 将无进位结果与进位左移后的结果相加，循环直到进位为 0。

注意处理负数时的符号位问题，进位计算需使用无符号类型避免移位溢出。

class Solution {
public:
    int getSum(int a, int b) {
        while(b){
            int x = a ^ b;              // 无进位相加的结果
            unsigned int carry = (unsigned int)(a & b) << 1; // 进位，转为无符号防止溢出
            a = x;
            b = carry;
        }
        return a;
    }
};

只出现一次的数字 II

思路分析： 数组中只有一个数出现一次，其余都出现三次。我们可以统计每一位上 1 出现的总次数。对于目标数 ret 的某一位，如果该位在数组所有数的对应位上总和模 3 余 1，则说明 ret 的这一位是 1，否则为 0。通过遍历 32 位即可还原出 ret。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for(int i = 0; i < 32; i++){ // 依次检查每一位
            int sum = 0;
            for(auto x : nums)
                if(x & (1 << i)) sum++;
            sum %= 3;
            if(sum & 1) ret |= 1 << i;
        }
        return ret;
    }
};

只出现一次的数字 III

思路分析：

1. 将所有数异或在一起，结果为两个只出现一次的数 a 和 b 的异或值 tmp = a ^ b。
2. a 不等于 b，所以 tmp 至少有一位为 1。找到这一位，它代表了 a 和 b 在该位上的二进制不同。
3. 根据这一位将数组分为两类，分别异或，即可得到 a 和 b。

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int tmp = 0;
        for(auto x : nums) tmp ^= x;
        
        // 找出 a, b 中比特位不同的那一位
        int diff = 0;
        while(1){
            if(((tmp >> diff) & 1) == 1) break;
            else diff++;
        }
        
        // 根据 diff 位的不同，将所有数划分成两类分别异或
        int a = 0, b = 0;
        for(auto x : nums){
            if((x >> diff) & 1) b ^= x;
            else a ^= x;
        }
        return {a, b};
    }
};

消失的两个数字

思路分析： 本题结合了'消失的数字'和'只出现一次的数字 III'。先将数组中的数和 [1, n+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;
        
        // 找出 a, b 中比特位不同的那一位
        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) b ^= x;
            else a ^= x;
        }
        for(int i = 1; i <= nums.size() + 2; i++){
            if((i >> diff) & 1) b ^= i;
            else a ^= i;
        }
        return {a, b};
    }
};