位运算在算法中的经典应用
1. 前置知识
熟练掌握位操作符（如 &, |, ^, ~, <<, >>）是理解以下算法的基础。建议先回顾位运算的基本逻辑与优先级。
2. 经典例题解析
2.1 判定字符是否唯一
核心思路： 利用【位图】思想，用一个整数的 32 个比特位代表字符集合。对于小写字母，仅需 26 位即可覆盖。若某位为 0 表示未出现，为 1 表示已出现。这相当于用整数充当哈希表。
注意利用鸽巢原理：若字符串长度超过 26，必然有重复字符，可直接返回 false。
class Solution {
public:
bool isUnique(string astr) {
// 利用鸽巢原理优化
if(astr.size() > 26) return false;
int bitmap = 0;
for(auto i : astr){
int e = i - 'a';
// 先判断字符是否出现过
if(((bitmap >> e) & 1) == 1) return false;
// 把当前字符加入到位图中
bitmap |= (1 << e);
}
return true;
}
};
2.2 消失的数字
核心思路： 数组大小为 n，包含 [0, n] 中缺失的一个数。利用异或运算的自反性（$a \oplus a = 0$），将数组所有元素与 [0, n] 的所有数字进行异或，成对的数字会相互抵消，最终结果即为缺失的数字。
class Solution {
public:
int missingNumber {
ret = ;
( i : nums) ret ^= i;
( i = ; i <= nums.(); i++) ret ^= i;
ret;
}
};
