算法优选：位运算技巧与实战案例

3. 两整数之和

问题核心： 不使用 + 和 - 运算符计算两个整数之和。

思路解析：

• 异或 (^) 本质是【无进位加法】。
• 按位与 (&) 配合左移能得到【进位】。
• 循环执行上述过程，直到进位变为 0，此时结果即为最终和。

注意处理负数时的符号位扩展问题，使用 unsigned int 辅助计算进位更稳妥。

class Solution {
public:
    int getSum(int a, int b) {
        while (b) {
            int x = a ^ b; // 无进位相加的结果
            // 排除-1 的情况，使用 unsigned 确保移位行为定义明确
            unsigned int carry = ((unsigned int)(a & b)) << 1;
            a = x;
            b = carry;
        }
        return a;
    }
};

4. 只出现一次的数字 II

问题核心： 数组中除一个元素外，其余每个元素都恰好出现三次，找出那个唯一的元素。

思路解析： 既然其他数字都出现了三次，那么对于任意一个比特位，所有数字在该位上的总和必然是 3 的倍数加上目标数字在该位的值（0 或 1）。 因此，我们可以统计每一位上 1 出现的次数，对 3 取模，余数即为目标数字对应位的值。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        // 依次检查 32 位的每一位
        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;
    }
};

5. 只出现一次的数字 III

问题核心： 数组中有两个元素只出现一次，其余都出现两次，找出这两个数。

思路解析：

1. 将所有数异或，结果为 a ^ b（因为成对的数抵消了）。
2. a 和 b 不相等，说明它们的二进制至少有一位不同。找到这个不同的位（例如最低位的 1）。
3. 根据这一位是 0 还是 1，将数组分为两组。a 和 b 会被分到不同组，相同的数会被分到同一组。
4. 分别对两组进行异或，即可得到 a 和 b。

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

6. 消失的两个数字

问题核心： 数组包含 [1, n+2] 中缺失的两个数。

思路解析： 这道题其实是前面两道题的组合。先将数组中的数和 [1, n+2] 区间内的所有数【异或】在一起，问题就转化为：有两个数出现了【一次】，其余所有的数出现了【两次】。这直接复用了解决'只出现一次的数字 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 (!((tmp >> diff) & 1)) diff++;
        
        // 3. 根据 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};
    }
};

位运算的魅力在于其高效性。掌握这些技巧后，面对相关类型的题目，你或许能一眼看穿本质，写出更优雅的代码。