位运算实战：判断字符唯一性与查找缺失数字
位运算是算法面试中的高频考点，尤其在处理状态压缩、集合操作和数值转换时，往往能带来 O(1) 的空间优化或常数级的时间提升。掌握异或、位移等基础操作，配合巧妙的逻辑设计，可以解决许多看似复杂的问题。
位运算基础前置知识
在深入题目之前，建议熟悉以下核心运算符及其特性：
- 与 (&)：用于掩码操作，提取特定位。
- 或 (|)：用于置位，将特定位设为 1。
- 非 (~)：按位取反。
- 异或 (^)：相同为 0，不同为 1，具有自反性（a ^ a = 0）。
- 左移 (<<) / 右移 (>>)：相当于乘以或除以 2 的幂次。
这些公式和推导建议大家结合代码多练习，形成肌肉记忆。
34. 判断字符是否唯一
题目描述：
给定一个字符串 astr，请实现一个算法，判断该字符串中所有字符是否都是唯一的。假设字符串只包含小写字母。
解题思路： 这道题的核心在于空间复杂度。如果允许使用额外的数据结构（如哈希表），问题很简单，但要求 O(1) 额外空间时，我们需要利用位图（Bit Map）的思想。
由于输入仅包含小写字母（共 26 个），而一个 int 类型变量有 32 位，足以容纳所有字符的状态映射。我们可以用一个整数 mask 来充当哈希表：
- 每一位代表一个字母（例如第 0 位代表 'a'，第 1 位代表 'b'）。
- 如果某一位是 0，表示该字符未出现过。
- 如果某一位是 1，表示该字符已出现过。
遍历字符串时，计算字符对应的偏移量 s - 'a'，检查对应位是否为 1。如果是，说明重复；否则将该位置 1。
C++ 代码实现：
class Solution {
public:
bool isUnique(string astr) {
// 如果长度超过 26，根据鸽巢原理必然有重复字符
if (astr.size() > 26) return false;
int mask = 0;
for (char s : astr) {
int bitIndex = s - 'a';
// 检查该位是否已被标记
if ((mask >> bitIndex) & 1) {
return false;
}
mask |= ( << bitIndex);
}
;
}
};
