位运算算法实战：从字符唯一性到双缺失数字求解

034 丢失的数字

题目描述： 给定包含 0, 1, ..., n 中 n 个不同整数的数组，找出缺失的那个数。

解题思路

利用异或运算的自反性（a ^ a = 0）。将数组中的所有元素与 0 到 n 的所有数字进行异或，成对的数字会相互抵消，最终剩下的就是缺失的那个数字。

代码实现

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int ret = 0;
        // 异或数组中的元素
        for (int x : nums) ret ^= x;
        // 异或 0 到 n 的所有数字
        for (int i = 0; i <= nums.size(); i++) ret ^= i;
        return ret;
    }
};

035 两整数之和

题目描述： 不使用运算符 + 和 -，计算两个整数之和。

解题思路

计算机加法本质上是「无进位加」加上「进位」。

• 异或 ^ 相当于无进位加法。
• 按位与 & 并左移一位 << 1 得到进位。
• 循环执行直到进位为 0。

注意处理负数时的符号位问题，使用 unsigned int 强制转换可避免未定义行为。

代码实现

class Solution {
public:
    int getSum(int a, int b) {
        while (b != 0) {
            int x = a ^ b;          // 无进位和
            unsigned int carry = (unsigned int)(a & b) << 1; // 进位
            a = x;
            b = carry;
        }
        return a;
    }
};

036 只出现一次的数字 II

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

解题思路

既然其他数字都出现了三次，那么对于每一个比特位，所有数字在该位上的 1 的总和必然是 3 的倍数，除非目标数字在该位上也是 1。

因此，我们可以遍历 32 个比特位，统计所有数字在该位上 1 的个数，对 3 取模。如果余数为 1，说明目标数字在该位是 1，否则是 0。

代码实现

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for (int i = 0; i < 32; i++) {
            int sum = 0;
            for (int x : nums) {
                if (((x >> i) & 1) == 1) sum++;
            }
            if (sum % 3 == 1) ret |= (1 << i);
        }
        return ret;
    }
};

037 消失的两个数字

题目描述： 给定一个包含 0, 1, ..., n 中 n 个不同整数的数组，缺失了两个数字，找出这两个数字。

解题思路

这是「丢失的数字」和「只出现一次的数字 III」的结合版。

1. 先将数组中的数和 1 到 n+2 区间内的所有数全部异或，得到的结果是两个缺失数字的异或值。
2. 找到这个异或结果中任意一个为 1 的比特位，这说明两个缺失数字在该位上不同。
3. 根据该位将原数组和完整序列分为两组，分别异或，即可得到两个缺失数字。

代码实现

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int tmp = 0;
        // 异或数组中的数
        for (int x : nums) tmp ^= x;
        // 异或 1 ~ N
        for (int i = 1; i <= nums.size() + 2; i++) tmp ^= i;
        
        // 找到不同的那一位
        int diff = 0;
        while (!((tmp >> diff) & 1)) diff++;
        
        int a = 0, b = 0;
        // 分组异或
        for (int 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};
    }
};

以上六道题涵盖了位运算在查找、去重、模拟加法等场景的核心应用。掌握异或消去律和位图思想，能显著提升解决此类问题的效率。