关于位操作和掩码（字符串查重）
目录
关于位操作和掩码（字符串查重）
0.1 背景
今天在 “力扣cn” 做了一道给字符串查重的题。
我的做法：
- 逐个字符地，把字符串转换成 HashSet（利用HashSet中元素不重复的特性）。
- 比较 “原字符串” 和 “HashSet” 的长度：
- 如果相同，说明没有重复；
- 如果不同，说明重复了。
public boolean isUnique(String astr) {
int stringLength = astr.length();
HashSet<Character> stringSet = new HashSet<>();
for (int i = 0; i < stringLength; i++) {
stringSet.add(astr.charAt(i));
}
// 比较二者长度，返回结果
if (stringLength == stringSet.size()) {
return true;
} else {
return false;
}
}比起用暴力双循环是好很多，自己还挺满意的，做完题看看解析，又发现了新天地：
- 虽然这样做，也能通过，而且执行效率排名还挺高；
- 但是，这其实并不是题目最初设计的考点，或者说还有更好的解法。
0.2 位移运算、位运算 和 掩码
这个解法还有一个重要前提，就是“只使用小写字母”（全大写字母也行。 “力扣cn” 在搬运的时候，忘了把这点加上）。
当我弄明白这个解法的时候，就像第一次写出 Hello World 时一样兴奋😮
public boolean bestSolution(String astr) {
int resultMask = 0;
// 初始化结果集（每一位全0：000...00）
for (int i = 0; i < astr.length(); i++) {
// 循环取出每个字符
char t = astr.charAt(i);
int offset = t - 'a';
// 算出该字符相对于字符'a'的偏移
int charMask = 1 << offset;
// 将"1"按照该偏移量左移，生成该字符对应的哪个位置是1（类似这样：0001...0000）
if ((resultMask & charMask) != 0) {
// 将 结果集 和 字符掩码 按位与运算（如果结果不等于0，则存在同为1的位，说明存在重复）
return false;
}
// resultBit |= charBit;
resultMask = resultMask | charMask;
// 将 结果集 和 字符掩码 按位或运算，结果赋值给结果集，相当于更新了结果集
}
return true;
}可以把结果集理解为一个与 “a ~ z” 按顺序对应的布尔类型的数组 boolean[] ，有助于理解。
0.3 再谈前提
然后我们再回头看这个重要前提，真实的限制，其实是 “字符串中，使用的字符，其 ASCII 码必须连续，且字符种类不能超过32”（但这样出题就太暴露意图了）。
如果使用33个连续字符，比如用 “ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`a” 进行测试，会得到 false 的结果。
原因是：由于溢出，a 使用了和 A 一样的掩码位，于是被程序判为重复。
所以，如果换成 long 类型，就可以支持到 64 种ASCII码连续的字符（然并卵）。
0.4 举一反三
这里其实用到一个很重要的概念：掩码
其实很多地方都会用到，比如：
- 数通网络里的 “子网掩码” 1，如果学过这块，理解起来应该更得心应手。
- Linux 文件夹权限也用到了掩码2。
- 这篇文章做了不错的拓展3：3鼠8瓶问题，和应用的权限控制（去年我写一个PHP项目的时候有类似想法，现在更通透了）。
位操作真是不简单，这是我第二次被位操作惊艳到了，上一次是 “不使用中间变量，交换两个变量的值”（我知道用加法，但不知道可以用位异或）。