位运算实战技巧
位运算不仅是底层优化的利器,更是解决特定算法问题的捷径。在处理大量数据或对性能要求极高的场景下,合理使用位操作往往能带来显著的空间和时间收益。下面我们通过几个经典题目,看看如何灵活运用这些技巧。
判定字符是否唯一
这道题的核心在于空间优化。既然只需要判断小写字母是否重复,我们可以用一个整数的 32 个比特位来充当哈希表。每一位代表一个字符,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';
// 先判断该位是否已被置为 1
if(((bitmap >> e) & 1) == 1) return false;
// 将当前字符对应的位设为 1
bitmap |= (1 << e);
}
return true;
}
};
寻找消失的数字
数组包含 [0, n] 中缺失的一个数。利用异或运算的自反性(a^a=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;
}
};

