判定字符是否唯一 -- 位运算

0x01.问题
实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

《程序员面试金典》01.02

0x02.简要分析
这是一个简单的问题，解决的办法比较多，比如双循环呀，利用C++的STL呀，或者使用各种标志容器记录呀，这里给出一种标志容器的方法：

var isUnique = function(astr) {
    let map = new Map();
    for(let i = 0; i < astr.length; i++) {
        if (map.has(astr[i])) {
            return false;
        }
        map.set(astr[i]);
        console.log(map)
    }
    return true;
};

时间的维度应该没得说了，但是空间的维度仍然有优化的余地。

我们使用的标志数组大小是26，我们要想优化，就必须有26个记录的点，但我们仔细想想，这26个数据中是不是都只使用了0或者1，其他的数字无意义，所以，我们可以考虑使用一个int类型的数据来存储这些0 1信息，一个int类型的数据是32位，完全足够存储这些信息，我们理清一下思路，我们需要的是利用这32位来记录这些信息，所以我们肯定要使用位运算，具体的思路如下：

初始化一个标志变量flag为0。
计算出每一个字符与‘a’的偏移量。
对数字1进行左移，左移的大小为偏移量。
这样我们就得到了一个只有相应位数上为1的二进制。
我们将这个左移后的数字与falg进行与操作。
这样，这个结果是否为0就由对应位数上的值是否为1决定，如果对应位数上不是1，说明这个字符是第一次操作，与操作的结果为0，此时将flag和偏移后的值进行或操作，就可以将对应位上的值置为1。
如果与操作结果不为0，说明之前这个位已经是1了，这个字符已经出现过，所以字符不唯一，直接返回false。
0x03.解决代码–位运算

var isUnique = function(astr) {
 
    let mark = 0;
    for (let char of astr) {
        // 需要左移的位数
        const c = char.charCodeAt() - 97;
        // mark 与 左移结果进行与运算，如果不是0，说明其中有一位都是1，说明重复
        if ((mark & (1 << c)) !== 0) {
        return false;
        }
        // 不重复，mark 与 左移结果 进行或运算，相当于保存该值
        mark = mark | (1 << c);
    }
    return true;

};

版权声明：本文为CSDN博主「ATFWUS」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/ATFWUS/article/details/105196665