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

判断字符是否唯一

题目描述： 给定一个字符串，判断其中所有字符是否都是唯一的。没有使用额外的数据结构。

解题思路

这道题的核心在于利用【位图】的思想。既然只涉及小写字母，我们可以用一个整数类型的变量来充当哈希表。一个 int 类型有 32 位，足够表示所有的小写字母（26 个）。

具体做法是：每一个比特位代表一个字符。如果某一位是 0，说明该字符还没出现过；如果是 1，说明已经出现过了。遍历字符串时，检查对应位的状态即可。

这里有个细节要注意：如果字符串长度超过 26，根据鸽巢原理，必然存在重复字符，可以直接返回 false。

C++ 代码实现

class Solution {
public:
    bool isUnique(string astr) {
        // 超过 26 个字符必然有重复
        if (astr.size() > 26) return false;
        
        int mask = 0;
        for (auto& c : astr) {
            int val = c - 'a';
            // 检查第 val 位是否为 1
            if ((mask >> val) & 1) return false;
            // 将第 val 位设为 1
            mask |= (1 << val);
        }
        return true;
    }
};

丢失的数字

题目描述： 给定包含 n 个不同数字的数组，这些数字取自 [0, 1, ..., n]，找出那个缺失的数字。

解题思路

这道题用异或运算非常巧妙。假设数组长度为 n，完整的序列应该是 [0, 1, ..., n]。

如果我们把数组中的所有元素，以及完整序列 [0, n] 中的所有数字全部进行异或操作，根据异或的'消消乐'性质（相同数字异或为 0），成对出现的数字都会抵消掉，最终剩下的结果就是那个缺失的数字。

这种方法不需要额外空间，时间复杂度也是线性的。

C++ 代码实现

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int ret = 0;
        // 先与数组中所有元素异或
        for (auto& n : nums) ret ^= n;
        // 再与 0 到 n 的所有数字异或
        for (size_t i = 0; i <= nums.size(); i++) ret ^= i;
        return ret;
    }
};