算法实战：位运算解决整数求和与缺失数字问题

算法实战：位运算解决整数求和与缺失数字问题

35. 两个整数之和

题目描述

不使用 + 或 - 运算符，计算两个整数的和。

示例

输入：a = 1, b = 2 输出：3

核心思路：位运算解法

这道题的核心在于理解计算机底层是如何做加法的。我们可以把加法拆解为两部分：无进位相加和进位。

1. 无进位和：使用异或运算 ^。比如 1 ^ 2 得到 3，这相当于不考虑进位的二进制加法。
2. 进位值：使用按位与 & 并左移一位 << 1。只有当两个位都是 1 时才会产生进位，且进位要加到更高一位上。
3. 循环处理：将无进位和作为新的 a，进位值作为新的 b，重复上述过程，直到进位为 0，此时 a 就是最终结果。

代码实现

class Solution {
public:
    int getSum(int a, int b) {
        // 当进位不为 0 时继续循环
        while (b != 0) {
            // 无进位相加的结果
            int sumWithoutCarry = a ^ b;
            // 计算进位位置，需要左移一位
            int carry = (unsigned int)(a & b) << 1;
            
            a = sumWithoutCarry;
            b = carry;
        }
        return a;
    }
};

注意：在 C++ 中，对有符号整数进行位移操作可能涉及未定义行为，这里为了安全起见，计算进位时建议先转为无符号类型再移位，或者确保逻辑符合补码规则。上面的逻辑在 LeetCode 环境下是安全的，但实际工程中需注意溢出边界。

流程解析

---

36. 只出现一次的数字 II

题目描述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

示例

输入：[2, 2, 3, 2] 输出：3

核心思路：比特位计数

既然其他数字都出现了三次，那么对于任意一个二进制位（bit），如果该位上的 1 被统计起来，其总和一定是 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;
            // 统计当前位上 1 的个数
            for (int x : nums) {
                sum += ((x >> i) & 1);
            }
            // 如果某一位的 1 的个数不是 3 的倍数，说明目标数字在这一位上是 1
            if (sum % 3 != 0) {
                ret |= (1 << i);
            }
        }
        return ret;
    }
};

流程解析

---

38. 消失的两个数字

题目描述

给定一个包含从 0 到 n 的所有整数中缺失了两个数字的数组，找出这两个缺失的数字。

示例

输入：nums = [1, 0] 输出：[2, 3] (顺序不限)

核心思路：分组异或

这个问题可以看作是'丢失的数字'和'只出现一次的数字 III'的结合版。

1. 整体异或：将数组中的所有数与 [1, n+2] 范围内的所有数进行异或。由于成对的数会抵消，最后得到的结果 ret 等于两个缺失数字的异或值（a ^ b）。
2. 区分两组：因为 a 和 b 不同，所以 ret 中至少有一位是 1。找到这个最右侧的 1 所在的位 x。
3. 分组异或：根据第 x 位是 0 还是 1，将所有数字分成两组。这样 a 和 b 必然会被分到不同的组中，而其他成对的数会在同一组内互相抵消。分别对两组进行异或，即可得到 a 和 b。

代码实现

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int ret = 0;
        // 第一步：计算所有数字与完整序列的异或结果
        for (int num : nums) {
            ret ^= num;
        }
        for (int i = 1; i <= nums.size() + 2; i++) {
            ret ^= i;
        }
        // 此时 ret = a ^ b
        
        // 第二步：找到 ret 中最右侧为 1 的位
        int diffBit = 0;
        while (((ret >> diffBit) & 1) == 0) {
            diffBit++;
        }
        
        int a = 0, b = 0;
        // 第三步：根据该位分组异或
        for (int num : nums) {
            if ((num >> diffBit) & 1) {
                a ^= num;
            } else {
                b ^= num;
            }
        }
        for (int i = 1; i <= nums.size() + 2; i++) {
            if ((i >> diffBit) & 1) {
                a ^= i;
            } else {
                b ^= i;
            }
        }
        
        return {a, b};
    }
};

流程解析