位运算核心原理与实战应用

丢失的数字

给定包含 [0, n] 中 n 个数的数组，找出缺失的那个数。除了哈希表或求和公式，利用异或运算的自反性（a ^ a = 0）也是极佳方案。

将数组所有元素与 0 到 n 的所有数字进行异或，成对的数字会抵消为 0，最终剩下的就是缺失的数字。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int ret = 0;
        for(auto x : nums) ret ^= x;
        for(int i = 0; i <= nums.size(); i++) ret ^= i;
        return ret;
    }
};

两整数之和

在不使用 + 和 - 的情况下计算两数之和。异或运算模拟无进位加法，与运算左移一位模拟进位。循环直到进位为 0。

class Solution {
public:
    int getSum(int a, int b) {
        while(b != 0) {
            int sum = a ^ b;              // 无进位和
            unsigned int carry = (unsigned int)(a & b) << 1; // 进位
            a = sum;
            b = carry;
        }
        return a;
    }
};

只出现一次的数字 II

数组中除某个元素外，其余均出现三次。我们需要线性时间且常数空间。思路是对每一位统计 1 出现的次数，模 3 后剩余的即为答案的对应位。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for(int i = 0; i < 32; i++) {
            int sum = 0;
            for(int x : nums)
                if(((x >> i) & 1) == 1)
                    sum++;
            if(sum % 3 == 1)
                ret |= (1 << i);
        }
        return ret;
    }
};

消失的两个数字

数组缺少两个数字，要求在 O(N) 时间和 O(1) 空间内找到它们。首先将所有数字异或，得到 a ^ b。根据结果中某一位为 1 的特征，将数字分为两组分别异或，即可分离出 a 和 b。

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

位运算的魅力在于它直接操作内存数据，理解这些底层逻辑能让你的算法设计更加高效。在实际编码中，遇到涉及状态压缩、奇偶性判断或性能敏感的场景，不妨多想想位运算的可能性。