位运算实战：两数之和、单次数字与缺失数字

35. 两个整数之和

题目链接

题目描述

不使用运算符 + 和 -，计算两整数 a、b 之和。

解题思路

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

1. 无进位相加：使用异或运算 ^。例如 1 ^ 1 = 0, 1 ^ 0 = 1，这正好对应二进制加法中不考虑进位的结果。
2. 进位计算：使用按位与 & 后左移一位 << 1。只有当两个位都是 1 时才会产生进位，且进位需要加到更高一位上。

我们需要不断重复这两个步骤，直到没有进位为止（即进位值为 0）。

C++ 代码实现

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++ 中，对有符号整数进行左移操作可能会触发未定义行为，因此建议将 a & b 的结果强制转换为 unsigned int 后再移位，以确保逻辑安全。

---

36. 只出现一次的数字 II

题目链接

题目描述

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

解题思路

既然其他数字都出现了三次，那么对于任意一个二进制位，如果该位上所有数字的 1 的个数能被 3 整除，说明目标数字在该位上是 0；否则，目标数字在该位上是 1。

我们可以遍历 32 个比特位，统计数组中所有数字在第 i 位上 1 出现的总次数。对 3 取余，结果即为唯一数字在该位的值。

C++ 代码实现

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);
            }
            // 如果 sum % 3 不为 0，说明目标数字该位为 1
            if (sum % 3 != 0) {
                ret |= (1 << i);
            }
        }
        return ret;
    }
};

---

38. 消失的两个数字

题目链接

题目描述

给定包含 0..n 中 n 个数的数组 nums，找出其中两个缺失的数字。

解题思路

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

1. 整体异或：将数组中的所有数字与 [1, n+2] 范围内的所有数字进行异或。根据异或性质 A ^ A = 0，成对出现的数字会抵消，最终结果 ret 等于两个缺失数字的异或值（a ^ b）。
2. 分组隔离：因为 a 和 b 不同，ret 中至少有一位是 1。找到这个位置（比如第 x 位），说明 a 和 b 在这一位上一个为 0，一个为 1。
3. 分别异或：利用这一位将原数组和范围数字分成两组。相同的数字必然在同一组，会互相抵消；而 a 和 b 会被分到不同组。分别对两组进行异或，即可得到 a 和 b。

C++ 代码实现

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int ret = 0;
        int a = 0;
        int b = 0;
        
        // 第一步：计算两个缺失数字的异或值
        for (int num : nums) {
            ret ^= num;
        }
        for (int i = 1; i <= nums.size() + 2; i++) {
            ret ^= i;
        }
        
        // 第二步：找到 ret 中最右侧为 1 的位
        int x = 0;
        while (((ret >> x) & 1) == 0) {
            x++;
        }
        
        // 第三步：根据该位将数字分为两组分别异或
        for (int num : nums) {
            if (((num >> x) & 1) == 0) {
                a ^= num;
            } else {
                b ^= num;
            }
        }
        for (int i = 1; i <= nums.size() + 2; i++) {
            if (((i >> x) & 1) == 0) {
                a ^= i;
            } else {
                b ^= i;
            }
        }
        
        return {a, b};
    }
};