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

36. 只出现一次的数字 II

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

题目描述

题目示例

解题思路

数组中除了一个元素只出现一次外，其余每个元素均出现三次。如果直接排序，时间复杂度较高。这里采用比特位计数的方法。

对于整数的每一个二进制位（共 32 位），统计数组中所有数字在该位上 1 出现的总次数。因为其他数字都出现了三次，所以它们在该位上的贡献必然是 3 的倍数。唯独那个只出现一次的数字，会让某一位的总和模 3 余 1。通过遍历 32 个位，我们就能还原出这个数字。

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);
            }
            // 模 3 后放回 ret 对应的位置
            ret |= ((sum % 3) << i);
        }
        return ret;
    }
};

流程解析

38. 消失的两个数字

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

题目描述

题目示例

解题思路

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

1. 整体异或：将数组中的所有数，以及 [1, n+2] 区间内的所有数全部异或一遍。由于成对出现的数会抵消，最终结果 ret 等于两个消失数字的异或值（a ^ b）。
2. 分组依据：因为 a 和 b 不同，它们的异或结果中至少有一位是 1。找到这个最右侧的 1，它代表了 a 和 b 在这一位上一个为 0，一个为 1。
3. 分组异或：根据这一位的值（0 或 1），将原数组和区间数分成两组分别异或。这样 a 和 b 就被分开了，而其他成对的数依然会在同一组内互相抵消。

C++ 代码实现

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int ret = 0;
        int a = 0;
        int b = 0;

        // 第一步：计算 a ^ b
        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++;

        // 第三步：根据第 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};
    }
};

流程解析

通过以上三道题目的讲解，我们可以看到位运算在算法设计中的强大之处。从模拟加法器到统计位频，再到利用异或特性分组，核心都是对数据底层二进制表示的直接操控。掌握这些技巧，往往能在特定约束下显著优化时间与空间效率。