位运算实战：算法题中的高效技巧

两整数之和

思路： 计算机底层加法本质上是位运算的组合。

• 异或 ^ 运算本质是【无进位加法】；
• 按位与 & 操作能够得到【进位】；
• 循环进行，直到【进位】变成 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

思路： 数组中只有一个数出现一次，其余都出现三次。统计所有数的【某一个比特位】的总和 % 3，结果即为目标数在该位的值（0 或 1）。遍历 32 位即可还原该数。

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。找到这一位 diff，说明 a 和 b 在此位上不同。
3. 根据 diff 位将数组分为两类，分别异或，即可得到 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++;
        }
        
        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 <= (int)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) b ^= x;
            else a ^= x;
        }
        for(int i = 1; i <= (int)nums.size() + 2; i++){
            if((i >> diff) & 1) b ^= i;
            else a ^= i;
        }
        return {a, b};
    }
};