在算法面试中，位运算往往能带来意想不到的空间和时间优化。掌握几个核心技巧，比如位图、异或消消乐，能解决很多看似复杂的难题。下面我们通过五个经典案例来深入理解这些操作。
1. 判定字符是否唯一
问题描述：给定一个字符串，判断其中是否包含重复字符。
思路解析 如果字符串长度超过 26，根据鸽巢原理，小写字母必然有重复，直接返回 false。否则，我们可以利用一个整数作为位图（BitMap），每一位代表一个小写字母。初始为 0，遇到某个字符就将对应位置 1。如果在设置前该位已经是 1，说明字符重复。
代码实现
public boolean isUnique(String astr) {
if (astr.length() > 26) return false;
int bitMap = 0;
for (int i = 0; i < astr.length(); i++) {
int x = astr.charAt(i) - 'a';
// 检查第 x 位是否为 1
if (((bitMap >> x) & 1) == 1) return false;
// 将第 x 位置为 1
bitMap |= (1 << x);
}
return true;
}
2. 丢失的数字
问题描述：数组包含从 0 到 n 的 n 个不同数字，其中缺少一个，找出缺失的那个。
思路解析
这里可以用到异或运算的特性：a ^ a = 0，a ^ 0 = a。如果我们把数组中的所有数字和 0 到 n 的所有数字都异或一遍，成对出现的数字会抵消为 0，最后剩下的就是那个只出现一次的缺失数字。
代码实现
public int missingNumber(int[] nums) {
;
( num : nums) {
ret ^= num;
}
( ; i <= nums.length; i++) {
ret ^= i;
}
ret;
}
