位运算算法实战
位运算在算法面试中属于高频考点，掌握其底层逻辑往往能带来 O(1) 空间复杂度的优化。本文精选了 6 道经典题目，涵盖字符判断、缺失值查找及整数运算模拟，带你深入理解异或、位掩码与比特位计数的实际应用。
033 判断字符是否唯一
题目描述： 给定一个字符串，判断其中所有字符是否都是唯一的。要求不使用额外的数据结构。
解题思路
利用「位图」思想，用一个整数的二进制位来代表字符状态。对于小写字母，int 类型的 32 位足以覆盖。若某一位为 1，表示对应字符已出现过；为 0 则未出现。
代码实现
class Solution {
public:
bool isUnique(string astr) {
// 鸽巢原理优化：超过 26 个字符必然有重复
if (astr.size() > 26) return false;
int bitMap = 0;
for (auto ch : astr) {
int i = ch - 'a';
// 检查该位是否已被置 1
if ((bitMap >> i) & 1) return false;
// 将该位置 1
bitMap |= (1 << i);
}
return true;
}
};
技术要点： 这里用位移和按位与操作替代了哈希表，空间复杂度降为 O(1)。注意
ch - 'a'将字符映射到 0-25 的索引。
034 丢失的数字
题目描述：
给定包含 0, 1, ..., n 中 n 个不同数字的数组，找出缺失的那个数字。
解题思路
利用异或运算的自反性：A ^ A = 0，A ^ 0 = A。将数组中的所有元素与 0 到 n 的所有数字进行异或，成对的数字会相互抵消，最终剩下的就是缺失的数字。
代码实现
{
:
{
ret = ;
( x : nums) ret ^= x;
( i = ; i <= nums.(); i++) ret ^= i;
ret;
}
};
