前置知识
做这类题之前，先把位运算的几个基本动作摸熟：与、或、异或、移位。它们不是'底层知识'这么简单，很多时候就是把原本要开数组、开哈希表的地方，压成一个整数就够了。
经典例题解析
判定字符是否唯一
如果直接用哈希表，空间复杂度是 O(N)。换成位图后，一个 32 位整数就能把小写字母的出现情况记下来，每一位只表示一个字符，0 是没出现，1 是出现过。
class Solution {
public:
bool isUnique(string astr) {
// 利用鸽巢原理优化，超过 26 个字符必然有重复
if(astr.size() > 26) return false;
int bitmap = 0;
for(auto i : astr){
int e = i - 'a';
// 检查该位是否已被置为 1
if(((bitmap >> e) & 1) == 1) return false;
// 将当前字符对应的位置 1
bitmap |= (1 << e);
}
return true;
}
};
这题的关键不在代码量，而在于别一上来就默认要'存起来'。字符集固定时，位图通常比哈希表更直接。
消失的数字
数组里缺了 [0, n] 中的一个数。这里用异或最顺手：相同数字异或会抵消成 0。把数组所有元素和完整序列 [0, n] 全部异或一遍，最后剩下的就是缺失值。
class Solution {
public:
int missingNumber(vector<int>& nums) {
int ret = 0;
( i : nums) ret ^= i;
( i = ; i <= nums.(); i++) ret ^= i;
ret;
}
};
