位运算在算法中的实战应用
位运算不仅是底层开发的基础，更是解决特定算法问题的高效手段。通过直接操作二进制位，我们往往能避开常规数据结构带来的开销，实现 O(1) 的空间复杂度或更优的时间效率。
前置知识回顾
在进行具体题目分析前，建议熟悉基本的位操作符：
- 按位与 (&)：常用于清零或提取特定位。
- 按位或 (|)：常用于置位。
- 异或 (^)：核心特性是相同为 0，不同为 1，具有自反性（a ^ a = 0）。
- 移位 (<<, >>)：相当于乘除 2 的幂次。
经典题解精选
1. 判定字符是否唯一
问题描述： 判断字符串中所有字符是否都是唯一的。
解题思路：
利用【位图】思想。小写字母共 26 个，一个 32 位的 int 变量足以容纳。每一位代表一个字符，0 表示未出现，1 表示已出现。
这里有个细节要注意：如果字符串长度超过 26，根据鸽巢原理，必然有重复字符，可直接返回 false。
class Solution {
public:
bool isUnique(string astr) {
// 鸽巢原理优化
if (astr.size() > 26) return false;
int bitmap = 0;
for (auto ch : astr) {
int idx = ch - 'a';
// 检查该位是否已被标记
if ((bitmap >> idx) & 1) return false;
// 将当前字符对应位置 1
bitmap |= (1 << idx);
}
return true;
}
};
2. 消失的数字
问题描述： 数组包含 [0, n] 中缺失的一个数。
解题思路： 利用异或的消去律。若将数组中的所有元素与 [0, n] 的所有数字全部异或，成对出现的数字会抵消为 0，最终剩下的就是缺失的那个数字。
{
:
{
ret = ;
( num : nums) ret ^= num;
( i = ; i <= nums.(); ++i) ret ^= i;
ret;
}
};
