位运算实战：判断字符唯一性与查找丢失数字

136. 只出现一次的数字

数组中除一个元素外，其余都出现两次。利用异或相同为 0、不同为 1 的特性，全部异或一遍即可得到目标值。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int val = 0;
        for(auto e : nums) {
            val ^= e;
        }
        return val;
    }
};

260. 只出现一次的数字 III

有两个数只出现一次，其余出现两次。思路是先全部异或得到两数之异或结果，找到其中一位为 1 的位（说明两数在该位不同），以此将数组分为两组分别异或。

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        if(nums.size() == 2) {
            return nums;
        }
        // 这里演示一种排序解法，虽然位运算更优，但排序逻辑直观
        sort(nums.begin(), nums.end());
        vector<int> res;
        int ans = 0;
        for(int i = 0; i < nums.size(); i++) {
            ans ^= nums[i];
        }
        for(int i = 0; i < nums.size(); i += 2) {
            if(nums[i] != nums[i + 1]) {
                res.push_back(nums[i]);
                ans ^= nums[i];
                break;
            }
        }
        res.push_back(ans);
        return res;
    }
};

实战一：判断字符是否唯一

题目描述： 实现一个算法，确定一个字符串的所有字符是否全都不同。假设字符串只包含小写字母。

解题思路： 既然只有小写字母（a-z），一共 26 个，而一个 int 类型有 32 位。我们可以把 int 当作一个位图（Bitmap）。每一位代表一个字母，如果某一位是 1，说明对应的字母出现过；如果是 0，则未出现。

具体做法是遍历字符串，对于每个字符，计算它相对于 'a' 的偏移量。检查该偏移量对应的位是否为 1，如果是，说明重复了；如果不是，将其置为 1。

代码实现：

class Solution {
public:
    bool isUnique(string astr) {
        // 如果字符数超过 26，根据鸽巢原理必然有重复
        if(astr.size() > 26) {
            return false;
        }
        int m = 0; // 作为比特位哈希表
        for(int i = 0; i < astr.size(); i++) {
            // 计算当前字符对应的位移
            int shift = astr[i] - 'a';
            // 检查该位是否已经是 1
            if((m >> shift) & 1) {
                return false;
            }
            // 将该位置为 1
            m |= (1 << shift);
        }
        return true;
    }
};

注意： 这种位图方法不需要额外的数据结构（如 HashSet），空间复杂度仅为 O(1)，非常适合字符集有限的场景。

实战二：丢失的数字

题目描述： 给定一个包含 [0, n] 中 n 个数的数组，找出 [0, n] 范围内没有出现在数组中的那个数。

解题思路： 这道题有多种解法，比如求和公式（高斯求和）或者排序。但位运算提供了一种非常优雅的方式。

利用异或运算的性质：A ^ A = 0，A ^ 0 = A。如果我们把数组中的所有数字，以及 [0, n] 范围内的所有数字全部异或在一起，那么成对出现的数字都会抵消为 0，最后剩下的就是那个缺失的数字。

代码实现：

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int ret = 0;
        // 初始化为 n，因为循环里只处理到 nums.size()-1，对应索引 i+1 最大为 n
        // 或者直接在循环里处理 0 到 n
        // 这里采用一种紧凑写法：ret 初始为 0，循环中异或 nums[i] 和 i+1
        // 注意：i 从 0 开始，对应数字应该是 0 到 n，所以我们需要额外处理 0 或者调整范围
        // 下面修正为更清晰的逻辑：
        ret = 0;
        for(int i = 0; i < nums.size(); i++) {
            ret ^= nums[i];      // 异或数组中的数
            ret ^= (i + 1);      // 异或 1 到 n 的数
        }
        ret ^= 0; // 补上 0，因为循环是从 1 开始的，0 没被异或进去
        return ret;
    }
};

优化版代码： 为了逻辑更清晰，避免修改输入或遗漏 0，推荐如下写法：

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int ret = 0;
        // 初始值为数组长度 n，相当于预先异或了 n
        ret = nums.size();
        for(int i = 0; i < nums.size(); i++) {
            ret ^= nums[i] ^ (i + 1);
        }
        return ret;
    }
};

总结： 通过这两道题，我们可以看到位运算在处理状态标记和数值抵消问题上的独特优势。位图思想用极小的空间换取了高效的查询能力，而异或消消乐则巧妙地利用了数学性质避免了额外的存储开销。在实际开发中，遇到类似'唯一性'、'成对出现'、'缺失值'的问题，不妨先想想能不能用位运算来简化方案。