位运算题三例：加法、单次数字与缺失数

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

逻辑复盘

36. 只出现一次的数字 II

题目链接

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

题目描述

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

题目示例

核心思路

这题的关键不在数组本身，而在二进制位。

如果其他数字都出现三次，那么任意一位上，1 出现的次数要么是 3 的倍数，要么会因为那个只出现一次的数字多出 1 次。于是我们只要把每一位单独统计出来，再对 3 取余，就能把目标数字拼回去。

这个做法不花额外空间，代价是固定扫 32 位。对面试题来说，这个取舍挺划算。

代码实现

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，其中有两个数字消失了，找出这两个消失的数字。

题目示例

核心思路

这题可以拆成两步看：先把两个缺失值的异或结果找出来，再把它们分到不同组里分别还原。

1. 先把数组里的数，和完整区间里的数一起异或。成对出现的部分都会抵消，最后剩下 a ^ b。
2. a ^ b 里一定有某一位是 1，找到这一位，就能把 a 和 b 分到两个组。
3. 数组和完整区间分别按这一位分组后再异或，两边各自会留下一个缺失数字。

这个思路不算短，但一旦你接受'异或会抵消'，后半段其实很顺。

代码实现

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

逻辑复盘

这三题放在一起看，重点其实不是'位运算很神'，而是你得知道它适合处理什么：一类题靠异或做抵消，一类题靠按位统计做还原，另一类题则是把加法拆成进位和非进位两部分。套路不多，但每个都挺实用。