位运算基础前置知识
在深入具体题目之前，建议先熟悉几个常用的位运算公式。这些操作符是后续解题的基石，理解它们的特性能帮你快速找到突破口。
34. 判断字符是否唯一
题目描述： 给定一个字符串，判断其中所有字符是否都是唯一的。没有使用额外的数据结构（如哈希表）的情况下，如何实现？
思路解析：
这道题的核心在于空间优化。既然输入只包含小写字母，我们可以利用位图（Bit Map）的思想。一个 int 类型有 32 位，足够表示 26 个小写字母的状态。每一位对应一个字符，0 代表未出现，1 代表已出现。
这样做的好处是不需要额外的数组或集合，直接用整数变量充当哈希表，将空间复杂度降到了 O(1)。
代码实现：
class Solution {
public:
bool isUnique(string astr) {
// 如果字符串长度超过 26，根据鸽巢原理必然有重复字符
if (astr.size() > 26) return false;
int mask = 0; // 用整数的比特位记录字符状态
for (char c : astr) {
int val = c - 'a'; // 计算字符对应的偏移量
// 检查该位是否已经是 1
if ((mask >> val) & 1) return false;
// 将该位置为 1
mask |= (1 << val);
}
return true;
}
};
注意：
实际运行时要注意边界条件，比如空字符串或长度超限的情况。这里直接返回 true 即可，原逻辑中的 -1 是笔误。
35. 丢失的数字
题目描述： 给定一个包含 [0, n] 中 n 个数的数组，找出缺失的那个数。
思路解析： 这道题非常适合用异或（XOR）运算来解决。异或有一个重要性质：相同的数异或结果为 0，任何数与 0 异或结果为其本身。
如果我们把数组中的所有元素，以及 [0, n] 范围内的所有数字全部放在一起异或，那么成对出现的数字都会抵消变成 0，最后剩下的那个非零值就是缺失的数字。这种方法既不需要额外空间，时间复杂度也是线性的。
代码实现：
class Solution {
public:
int missingNumber(vector<int>& nums) {
int ret = 0;
// 先异或数组中的所有元素
for (int n : nums) ret ^= n;
// 再异或 0 到 n 的所有索引
for (size_t i = 0; i <= nums.size(); ++i) ret ^= i;
return ret;
}
};
总结： 通过这两道题，我们可以看到位运算在处理特定约束下的数据问题时非常高效。位图适合做状态标记，而异或适合做消除和查找。掌握这些技巧，能在面试中快速给出最优解。
