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

题目链接

题目描述

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

解题思路

既然其他数字都出现了三次，那么对于任意一个二进制位，如果该位上所有数字的 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};
    }
};