算法实战：位运算解决两数之和、唯一数字及缺失数字

代码实现

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，则目标数字该位为 1
            if (sum % 3 == 1) {
                ret |= (1 << i);
            }
        }
        return ret;
    }
};

38. 消失的两个数字

题目描述

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

核心思路

这道题其实是「丢失的数字」和「只出现一次的数字 III」的结合体。

1. 整体异或：将数组中的所有数字与 [1, n+2] 范围内的所有数字进行异或。由于成对出现的数字异或后为 0，剩下的结果就是那两个缺失数字的异或值（记为 ret）。
2. 分组策略：因为两个缺失数字不同，ret 的二进制表示中至少有一位是 1。找到这一位（通常是最低位的 1），根据这一位是 0 还是 1，将所有数字分成两组。
3. 分别异或：两组数字分别进行异或操作，每一组中都会包含一个缺失数字和其他成对的数字。最终每组异或的结果就是其中一个缺失数字。

代码实现

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int ret = 0;
        int a = 0;
        int b = 0;
        
        // 第一步：计算两个缺失数字的异或值
        for (int x : nums) {
            ret ^= x;
        }
        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};
    }
};

总结

这三道题展示了位运算在算法设计中的强大之处：

• 两数之和：用异或模拟加法，用与运算处理进位，彻底摆脱了算术运算符的限制。
• 唯一数字 II：通过比特位计数模 3，将全局统计问题转化为局部位判断，实现了 O(1) 空间解法。
• 消失的两个数字：利用异或消去相同项的特性，结合分组思想，将复杂问题拆解为简单的子问题。

掌握这些技巧，面对类似的位操作面试题时就能游刃有余。