位运算在算法优化中的实战应用

3. 两整数之和

题目链接： LeetCode - Sum of Two Integers

解题思路

在不使用 + 和 - 运算符的情况下求和，本质是模拟加法器的逻辑。

1. 无进位加法：由异或 ^ 实现。
2. 进位计算：由按位与 & 并左移 << 1 得到。
3. 循环迭代：直到进位变为 0，此时结果即为最终和。

注意处理负数时，C++ 中右移可能涉及符号位扩展，但左移进位时使用 unsigned int 能避免未定义行为。

class Solution {
public:
    int getSum(int a, int b) {
        while (b) {
            int x = a ^ b;              // 无进位相加的结果
            unsigned int carry = (unsigned int)(a & b) << 1; // 进位
            a = x;
            b = carry;
        }
        return a;
    }
};

4. 只出现一次的数字 II

题目链接： LeetCode - Single Number II

解题思路

数组中除一个元素外，其余都出现了三次。我们需要找到那个只出现一次的数。

统计每一位上 1 出现的总次数。对于目标数字的某一位，如果它在数组中只出现一次，那么该位在所有数字中的总和模 3 应该等于 1；否则为 0。通过遍历 32 个比特位，即可还原出目标数字。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for (int i = 0; i < 32; i++) { // 依次检查每一位
            int sum = 0;
            for (auto x : nums) {
                if (x & (1 << i)) sum++;
            }
            if (sum % 3) ret |= (1 << i);
        }
        return ret;
    }
};

5. 只出现一次的数字 III

题目链接： LeetCode - Single Number III

解题思路

这次有两个数字只出现一次，其余均出现两次。首先将所有数异或，得到的结果是这两个数的异或值 a ^ b。

因为 a != b，所以 a ^ b 至少有一位是 1。找到这个不同的比特位（例如第 diff 位），就可以根据这一位是 0 还是 1，将原数组分为两组。相同的数字必然在同一组，而 a 和 b 会被分到不同组。分别对两组进行异或，即可得到结果。

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int tmp = 0;
        for (auto x : nums) tmp ^= x;

        // 找出 a, b 中二进制不同的那一位
        int diff = 0;
        while (!((tmp >> diff) & 1)) diff++;

        int a = 0, b = 0;
        for (auto x : nums) {
            if ((x >> diff) & 1) b ^= x;
            else a ^= x;
        }
        return {a, b};
    }
};

6. 消失的两个数字

题目链接： LeetCode - Missing Two

解题思路

这道题其实是上述两个问题的组合。先将数组中的数和 1 到 n+2 区间内的所有数【异或】在一起，问题就转化为：有两个数出现了一次，其余出现了两次。这直接复用了解决'只出现一次的数字 III'的逻辑，只需在分组异或时，将 1 到 n+2 的序列也参与分组即可。

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int tmp = 0;
        for (auto x : nums) tmp ^= x;
        for (int i = 1; i <= nums.size() + 2; i++) tmp ^= i;

        // 找出 a, b 中比特位不同的那一位
        int diff = 0;
        while (!((tmp >> diff) & 1)) diff++;

        int a = 0, b = 0;
        for (auto x : nums) {
            if ((x >> diff) & 1) b ^= x;
            else a ^= x;
        }
        for (int i = 1; i <= nums.size() + 2; i++) {
            if ((i >> diff) & 1) b ^= i;
            else a ^= i;
        }
        return {a, b};
    }
};

位运算虽然底层，但在算法竞赛和工程优化中非常实用。掌握这些技巧，往往能让你的代码在时间和空间上都更上一层楼。