力扣判断字符是否唯一(位运算)

今天我们通过判断字符是否唯一这个题来了解位运算的一些性质。
在做题之前我们需要先解决两个问题。

给一个数n,判断它的二进制位中第x位是0还是1(从0开始计数)

如果我们需要判断第4位是0还是1，我们只需要将n右移三位，然后和1按位与就可以了。

（n>>x）&1

先将n右移X位再按位与

将一个数n的二进制位第X位修改为1(从0开始计数)

实现方式：

n=n|(1<<x)

先将1左移X-1位再与n按位或

将一个数n的二进制第x位修改为0(从0开始计数)

实现方式：

n=n&(~(1<<x))

将1左移X-1位取反再按位与
大家可以自己举例子尝试

提取一个数n二进制中最右侧的1

实现方式：

n&(-n)

去掉一个数n二进制表示中最右侧的1

实现方式：

n&(n-1)

接下来运用上面的规律来解决判判断字符是否唯一这道题
实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

示例 1：
输入: s = “leetcode”
输出: false
示例 2：
输入: s = “abc”
输出: true
限制：
0 <= len(s) <= 100
s[i]仅包含小写字母
如果你不使用额外的数据结构，会很加分。
解题思路：

因为只有26个小写字母，int 类型有32个比特位，所以我们可以将32个比特位看作一个哈希表（这个是思路有个名字叫位图），然后遍历字符串，如果字符第一次出现就将该字符对应的比特位改为1（例如字符‘a’对应的是0下标），没有出现的比特位就是0，这样我们只需要判断该字符对应的比特位是否是1，就可以判断字符串是否重复。

代码实现：

class Solution {public boolean isUnique(String astr) {int ret=0;if((astr.length())>26){return false;}char[] str=astr.toCharArray();for(char ch:str){int i=ch-'a';if(((ret>>i)&1)==1)//判断字符在之前是否出现过{return false;}ret|=1<<i;//字符第一次出现将对应的比特位初始为1}return true;}
}

大家有什么看法意见可以留言评论。