算法优选：位运算实战技巧

位运算在算法中的经典应用

1. 前置知识

熟练掌握位操作符（如 &, |, ^, ~, <<, >>）是理解以下算法的基础。建议先回顾位运算的基本逻辑与优先级。

2. 经典例题解析

2.1 判定字符是否唯一

核心思路： 利用【位图】思想，用一个整数的 32 个比特位代表字符集合。对于小写字母，仅需 26 位即可覆盖。若某位为 0 表示未出现，为 1 表示已出现。这相当于用整数充当哈希表。

注意利用鸽巢原理：若字符串长度超过 26，必然有重复字符，可直接返回 false。

class Solution {
public:
    bool isUnique(string astr) {
        // 利用鸽巢原理优化
        if(astr.size() > 26) return false;
        
        int bitmap = 0;
        for(auto i : astr){
            int e = i - 'a';
            // 先判断字符是否出现过
            if(((bitmap >> e) & 1) == 1) return false;
            // 把当前字符加入到位图中
            bitmap |= (1 << e);
        }
        return true;
    }
};

2.2 消失的数字

核心思路： 数组大小为 n，包含 [0, n] 中缺失的一个数。利用异或运算的自反性（$a \oplus a = 0$），将数组所有元素与 [0, n] 的所有数字进行异或，成对的数字会相互抵消，最终结果即为缺失的数字。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int ret = 0;
        // 异或数组中的所有元素
        for(auto i : nums) ret ^= i;
        // 异或 [0, n] 范围内的所有数字
        for(int i = 0; i <= nums.size(); i++) ret ^= i;
        return ret;
    }
};

2.3 两整数之和

核心思路： 计算机底层加法由两部分组成：无进位和与进位。

• 异或 ^ 得到无进位加法结果。
• 按位与 & 左移一位 << 1 得到进位值。 循环执行直到进位为 0。

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

2.4 只出现一次的数字 II

核心思路： 数组中除一个元素外，其余都出现三次。我们需要统计每一位上 1 出现的总次数。如果某一位的 1 的总数能被 3 整除，说明目标数该位为 0；否则为 1。

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++;
            sum %= 3;
            if(sum & 1) ret |= (1 << i);
        }
        return ret;
    }
};

2.5 只出现一次的数字 III

核心思路：

1. 全部异或得到 $a \oplus b$（假设两个单独数为 a, b）。
2. 找到 $a \oplus b$ 中任意一个为 1 的位（即 a, b 不同的位）。
3. 根据该位将数组分为两组，分别异或，即可还原 a 和 b。

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int tmp = 0;
        for(auto x : nums) tmp ^= x;
        
        int diff = 0;
        while(1){
            if(((tmp >> diff) & 1) == 1) break;
            else diff++;
        }
        
        int a = 0, b = 0;
        for(auto x : nums){
            if((x >> diff) & 1) b ^= x;
            else a ^= x;
        }
        return {a, b};
    }
};

2.6 消失的两个数字

核心思路： 本题结合了'消失的数字'与'只出现一次的数字 III'。 先将数组元素与 [1, n+2] 区间所有数异或，问题转化为寻找两个只出现一次的数。后续步骤同 2.5，只需额外对区间内的数字也进行分组异或处理。

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(1){
            if(((tmp >> diff) & 1) == 1) break;
            else 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};
    }
};