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

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

37. 消失的两个数字

题目描述

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

解题思路

这道题可以看作是'丢失的数字'和'只出现一次的数字 III'的结合体。核心思路依然是利用异或运算的特性：相同的数异或为 0。

1. 首先将数组中的所有数字与 1 到 n+2 区间内的所有数字进行异或。由于除了两个缺失数字外，其他数字都出现了两次（一次在数组，一次在区间），它们会互相抵消。
2. 最终得到的结果 ret 就是两个缺失数字的异或值 a ^ b。
3. 因为 a 和 b 不同，ret 中至少有一位是 1。找到这个最右侧的 1，根据这一位将数字分为两组。
4. 分别对这两组进行异或，就能得到 a 和 b。

代码实现

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int ret = 0;
        int a = 0;
        int b = 0;
        
        // 第一步：异或所有数组元素和区间元素，得到 a ^ b
        for (int num : nums) {
            ret ^= num;
        }
        for (int i = 1; i <= nums.size() + 2; i++) {
            ret ^= i;
        }
        
        // 第二步：找到 ret 中最右侧为 1 的位
        int diffBit = 0;
        while (((ret >> diffBit) & 1) == 0) {
            diffBit++;
        }
        
        // 第三步：根据该位分组异或
        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};
    }
};

通过以上三个例子，我们可以看到位运算在处理整数问题时的高效性。无论是避免进位的加法、统计比特位分布，还是利用异或消除重复项，掌握这些技巧都能让代码更简洁、性能更优。在实际开发中，遇到相关场景不妨多想想位运算的可能性。