位运算算法实战：经典题目深度解析

两整数之和

问题描述： 不使用 + 和 - 运算符计算两个整数的和。

核心思路：

• 异或 ^ 本质是【无进位加法】；
• 按位与 & 配合左移能得到【进位】；
• 循环执行直到进位变为 0。

注意处理负数时的符号位扩展问题，使用 unsigned int 存储进位更安全。

class Solution {
public:
    int getSum(int a, int b) {
        while (b) {
            int x = a ^ b;              // 无进位相加的结果
            unsigned int carry = (a & b) << 1; // 计算进位
            a = x;
            b = carry;
        }
        return a;
    }
};

只出现一次的数字 II

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

核心思路： 统计每一位上 1 出现的总次数。对于目标数字的某一位，如果它在数组中出现一次，那么该位总和 % 3 应该等于 1；否则为 0。通过遍历 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。
2. 找到 a 和 b 二进制中不同的某一位（即异或结果中为 1 的位）。
3. 根据这一位将数组分为两组，分别异或，即可得到两个答案。

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

消失的两个数字

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

核心思路： 这道题是前两道题的组合。先将数组中的数和 [1, n+2] 区间内的所有数【异或】在一起，问题就转化为'有两个数出现一次，其余出现两次'，直接复用上述分组策略即可。

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