C++ 位运算详解：基础题解与思维分析
第一章：位运算基础应用
1.1 判断字符是否唯一（easy）
题目描述：
实现一个算法，确定一个字符串 s 的所有字符是否全都不同。
示例 1：
- 输入：
s = "leetcode" - 输出：
false
示例 2：
- 输入：
s = "abc" - 输出：
true
提示：
0 <= len(s) <= 100s[i]仅包含小写字母- 如果不使用额外的数据结构，会很加分。
解法（位图的思想）
算法思路：
利用「位图」的思想，每一个「比特位」代表一个「字符」，一个 int 类型的变量的 32 位足够表示所有的小写字母。在位图中，如果一个比特位是 0，表示这个字符没有出现过；如果一个比特位是 1，表示该字符出现过。
因此，我们可以使用一个「整数」来充当「哈希表」：
- 字符映射：每个字符的出现与否可以映射到一个
bitMap中的比特位上。 - 位运算操作：
- 检测：检测字符是否已经出现过，使用
((bitMap >> i) & 1) == 1来检查第i位。 - 添加字符：使用
bitMap |= 1 << i将字符加入到bitMap中。
- 检测：检测字符是否已经出现过，使用
- 鸽巢原理优化：当字符串长度超过 26 时，必定有重复字符，可以直接返回
false。
C++ 代码实现
class Solution {
public:
bool isUnique(string astr) {
// 利用鸽巢原理来做的优化
if (astr.size() > 26) return false;
int bitMap = 0;
for (auto ch : astr) {
int i = ch - 'a';
(((bitMap >> i) & ) == ) ;
bitMap |= << i;
}
;
}
};
