算法实战：位运算解决字符唯一性与丢失数字问题

位运算基础前置知识

在深入题目之前，先回顾几个常用的位运算公式。这些是后续解题的基石，建议结合图示理解。

上面提到的几个核心公式大家可以先记下来，推导过程不必死磕，重在应用。

34. 判断字符是否唯一

题目链接： 面试题 01.01. 判定字符是否唯一 - 力扣（LeetCode）

题目描述： 实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

题目示例：

解法（位图的思想）

算法思路

这道题如果允许使用额外数据结构，用哈希表很容易解决。但为了追求极致空间效率，我们可以利用【位图】思想。

假设输入只包含小写字母，那么最多只有 26 种可能。一个 int 类型变量有 32 位，足够表示所有的小写字母状态。每一位代表一个字符：

• 比特位为 0：表示该字符未出现过。
• 比特位为 1：表示该字符已出现过。

这样，我们用一个整数就能充当哈希表，空间复杂度降为 O(1)。

C++ 算法代码

class Solution {
public:
    bool isUnique(string astr) {
        // 如果长度超过 26，根据鸽巢原理必有重复
        if (astr.size() > 26) return false;
        
        int m = 0;
        for (auto& s : astr) {
            // 检查对应位是否已被置 1
            if ((m >> (s - 'a')) & 1) return false;
            // 否则将该位置 1
            else m |= (1 << (s - 'a'));
        }
        return true;
    }
};

这里有个细节要注意：原逻辑中若发现重复直接返回 false，遍历结束则说明无重复，应返回 true。另外，由于题目通常限定为小写字母，提前判断长度大于 26 可以快速剪枝。

35. 丢失的数字

题目链接： 268. 丢失的数字 - 力扣（LeetCode）

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

题目示例：

解法（位运算）

算法思路

设数组大小为 n，缺失前的完整序列应该是 [0, n]。现在数组中缺失了一个数。

如果我们把数组中的所有元素，以及 [0, n] 范围内的所有数字全部进行【异或】运算，会发生什么？

根据异或运算的性质：

1. a ^ a = 0
2. a ^ 0 = a

除了缺失的那个数，其他所有数字都会在'数组部分'和'完整序列部分'各出现一次，相互抵消变为 0。最终剩下的结果就是缺失的那个数字。

这种方法不需要额外空间，且时间复杂度仅为 O(n)。

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

实际运行时会发现，这种写法比求和公式更稳健，完全避免了整数溢出的风险。

总结

这两道题是位运算的经典入门案例。第一题展示了如何用位图压缩空间，第二题展示了异或消去法的巧妙之处。掌握这些技巧，在处理底层数据或性能敏感场景时会有很大帮助。