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

注意：在 C++ 中，对有符号整数进行左移可能涉及未定义行为，建议将 a & b 的结果强制转换为无符号类型后再移位，或者确保输入范围安全。

逻辑复盘

36. 只出现一次的数字 II

题目链接

137. 只出现一次的数字 II - LeetCode

题目描述

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

题目示例

核心思路

既然其他数字都出现了三次，那么对于二进制表示的任意一位，所有数字在该位上的 1 出现的总次数必然是 3 的倍数，除非那个唯一的数字在该位上是 1。

因此，我们可以遍历整数的 32 个比特位，统计数组中所有数字在第 i 位上 1 的个数。如果这个计数对 3 取余不为 0，说明目标数字在该位上是 1，否则为 0。通过这种方式逐位还原出目标数字。

代码实现

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

逻辑复盘

38. 消失的两个数字

题目链接

面试题 17.19. 消失的两个数字 - LeetCode

题目描述

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

题目示例

核心思路

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

1. 整体异或：将数组中的所有数与 [1, n+2] 区间内的所有数一起进行异或运算。由于成对的数字会相互抵消，剩下的结果就是两个消失数字的异或值 ret = a ^ b。
2. 区分分组：因为 a 和 b 不同，ret 中至少有一位是 1。找到 ret 最右侧为 1 的比特位，这意味着 a 和 b 在这一位上一个为 0，一个为 1。
3. 分组异或：根据这一位是 0 还是 1，将原数组和 [1, n+2] 区间的所有数分成两组。分别对两组进行异或，每组最终剩下的结果就是其中一个消失的数字。

代码实现

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 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};
    }
};

逻辑复盘

通过以上三个案例可以看出，位运算不仅仅是简单的语法操作，更是解决特定约束下（如空间复杂度）问题的有力工具。掌握异或消去、进位模拟和比特位统计这三种模式，能应对大部分相关算法场景。