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

位运算实战技巧

位运算不仅是底层优化的利器，更是解决特定算法问题的捷径。在处理大量数据或对性能要求极高的场景下，合理使用位操作往往能带来显著的空间和时间收益。下面我们通过几个经典题目，看看如何灵活运用这些技巧。

判定字符是否唯一

这道题的核心在于空间优化。既然只需要判断小写字母是否重复，我们可以用一个整数的 32 个比特位来充当哈希表。每一位代表一个字符，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';
            // 先判断该位是否已被置为 1
            if(((bitmap >> e) & 1) == 1) return false;
            // 将当前字符对应的位设为 1
            bitmap |= (1 << e);
        }
        return true;
    }
};

寻找消失的数字

数组包含 [0, n] 中缺失的一个数。利用异或运算的自反性（a^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;
    }
};

两整数之和

在没有加减乘除运算符的情况下如何实现加法？这其实是在模拟 CPU 的加法器逻辑。异或运算实现了无进位加法，而按位与左移则计算出了进位值。只要进位不为 0，就继续循环相加。

class Solution {
public:
    int getSum(int a, int b) {
        while(b){
            int x = a ^ b; // 无进位结果
            // 计算进位，需转为 unsigned 避免符号位干扰
            unsigned int carry = (unsigned int)(a & b) << 1; 
            a = x;
            b = carry;
        }
        return a;
    }
};

只出现一次的数字 II

数组中只有一个数字出现一次，其余都出现三次。这时候不能简单用异或了，因为 x^x^x=x。我们需要统计每一位上 1 出现的总次数，然后对 3 取模。如果某一位的总和模 3 余 1，说明目标数字在该位是 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;
    }
};

只出现一次的数字 III

这次有两个数字各出现一次，其余出现两次。首先将所有数异或，得到的结果是这两个不同数字的异或值 a^b。由于 a!=b，这个结果中至少有一位是 1。找到这一位，就可以把原数组分成两组：该位为 0 的和该位为 1 的。这样两个目标数字会被分到不同的组，而相同的数字依然在同一组，分别异或即可得到结果。

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int tmp = 0;
        for(auto x : nums) tmp ^= x;
        
        // 找出最低位的不同位
        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};
    }
};

消失的两个数字

这是前面两个问题的组合变体。先将数组元素与 [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;
        
        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};
    }
};