算法优选：位运算实战技巧与经典例题解析

前言

在算法面试和实际开发中，位运算往往是被低估的利器。它不仅能将空间复杂度优化到 O(1)，还能在某些场景下显著提升执行效率。今天我们就通过几道经典的力扣题目，深入聊聊位运算的核心思想与实战应用。

一、判定字符是否唯一

题目： 给定一个字符串，判断其中所有字符是否都是唯一的。

思路： 利用【位图】的思想，每一个【比特位】代表一个【字符】。由于题目通常限定为小写字母，一个 int 类型的变量有 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;
    }
};

二、消失的数字

题目： 数组包含 [0, n] 中缺失的一个数，找出这个缺失的数字。

思路： 设数组大小为 n，原本应该是 [0, n] 的序列。如果我们把数组中的所有数，以及 [0, n] 的所有数全部【异或】在一起，根据异或运算的【消消乐】规则（相同数字异或为 0），最终剩下的结果就是缺失的那个数字。

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

三、两整数之和

题目： 不使用 + 和 - 运算符计算两个整数的和。

思路： 这是考察二进制加法本质的经典题。

• 异或 (^) 运算本质是【无进位加法】。
• 按位与 (&) 操作能够得到【进位】。
• 然后一直循环进行，直到【进位】变成 0 为止。

注意处理负数时的符号位扩展问题，C++ 中右移负数是实现定义的，所以进位部分要强制转为 unsigned int。

class Solution {
public:
    int getSum(int a, int b) {
        while(b){
            int x = a ^ b; // 无进位相加的结果
            // 排除 -1 的情况，进位需无符号移位
            unsigned int carry = (unsigned int)(a & b) << 1;
            a = x;
            b = carry;
        }
        return a;
    }
};

四、只出现一次的数字 II

题目： 数组中除一个元素只出现一次外，其余每个元素均出现三次。

思路： 既然其他数字都出现了三次，那么对于任意一个比特位，所有数字在该位上的 1 的总和一定是 3 的倍数加上目标数字在该位的值。 因此，我们可以统计每一位上 1 出现的次数，对 3 取模，余数即为目标数字在该位的值。这样逐位还原出目标数。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for(int i = 0; i < 32; i++){ // 依次修改 ret 中的每一位
            int sum = 0;
            for(auto x : nums) // 计算 nums 中所有第 i 位的和
                if(x & (1 << i)) sum++;
            
            sum %= 3;
            if(sum & 1) ret |= (1 << i);
        }
        return ret;
    }
};

五、只出现一次的数字 III

题目： 数组中只有两个元素只出现一次，其余都出现两次。

思路：

1. 将所有数异或在一起，结果为 a ^ b（因为成对的数异或抵消了）。
2. a 和 b 不相等，说明它们的二进制中至少有一位不同。找到这一位（例如 diff）。
3. 根据 diff 位是 0 还是 1，将数组分为两组。a 和 b 会被分到不同的组，而相同的数一定会被分到同一组。
4. 分别对两组进行异或，即可得到 a 和 b。

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        // 1. 将所有的数异或在一起
        int tmp = 0;
        for(auto x : nums) tmp ^= x;
        
        // 2. 找出 a，b 中比特位不同的那一位
        int diff = 0;
        while(1){
            if(((tmp >> diff) & 1) == 1) break;
            else diff++;
        }
        
        // 3. 根据 diff 位的不同，将所有数划分成两类
        int a = 0, b = 0;
        for(auto x : nums){
            if((1 & (x >> diff)) == 1) b ^= x;
            else a ^= x;
        }
        return {a, b};
    }
};

六、消失的两个数字

题目： 数组包含 [1, n+2] 中缺失的两个数字。

思路： 这道题其实是前面两道题的组合。 先将数组中的数和 [1, n+2] 区间内的所有数【异或】在一起，问题就变成了：有两个数出现了【一次】，其余所有的数出现了【两次】。这直接转化为了'只出现一次的数字 III'模型，后续步骤完全一致。

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        // 1. 将所有的数异或在一起
        int tmp = 0;
        for(auto x : nums) tmp ^= x;
        for(int i = 1; i <= nums.size() + 2; i++) tmp ^= i;
        
        // 2. 找出 a，b 中比特位不同的那一位
        int diff = 0;
        while(1){
            if(((tmp >> diff) & 1) == 1) break;
            else diff++;
        }
        
        // 3. 根据 diff 位的不同，将所有数划分成两类
        int a = 0, b = 0;
        for(auto x : nums){
            if((1 & (x >> diff)) == 1) b ^= x;
            else a ^= x;
        }
        for(int i = 1; i <= nums.size() + 2; i++){
            if((1 & (i >> diff)) == 1) b ^= i;
            else a ^= i;
        }
        return {a, b};
    }
};

总结

位运算不仅仅是底层的魔法，更是解决特定约束下算法问题的关键钥匙。掌握异或的性质、位图的压缩存储以及进位逻辑，能让你在面对空间敏感型问题时游刃有余。建议在实际编码中多尝试用位运算替代常规逻辑，往往会有意想不到的性能提升。