简单的位运算，但是不懂原理

在看判断一个字符串中的字符是否唯一（只用基本数据结构）的程序中，发现它用了位运算来求解，自己动手算了一下，但是自己对于位运算接触的太少，不解其中的原理，请教各位，程序里左移是为什么呢？这个程序的基本思想是什么呀？谢谢！

1.   public static boolean isUniqueChars(String str) {
   
2.     int checker = 0;
   
3.     for (int i = 0; i < str.length(); ++i) {
   
4.       int val = str.charAt(i) - ‘a’;
   
5.       if ((checker & (1 << val)) > 0) return false;
   
6.       checker |= (1 << val);
   
7.     }
   
8.     return true;
   
9.   }

复制代码

这是用每一个bit对应字符. 如果出现过，那么checker上这个bit就为1，不然就是0. 这里应该是假设所有输入都只有小写字符，不然31个bit装不下48个字符

rogerdai 发表于 2015-7-19 23:19
这是用每一个bit对应字符. 如果出现过，那么checker上这个bit就为1，不然就是0. 这里应该是假设所有输入都 ...

恍然大悟啊，它确实假设了只有小写字母，谢谢！

位运算很好玩，习惯了以后你会喜欢的~~

zhuli19901106 发表于 2015-7-20 00:49
位运算很好玩，习惯了以后你会喜欢的~~

请问一下这个题你们是第一次做的时候就想到这个位运算的方法了？

rogerdai 发表于 2015-7-19 23:19
这是用每一个bit对应字符. 如果出现过，那么checker上这个bit就为1，不然就是0. 这里应该是假设所有输入都 ...

请问一下这个题你们是第一次做的时候就想到这个位运算的方法了？

水逼一枚 发表于 2015-7-20 14:20
请问一下这个题你们是第一次做的时候就想到这个位运算的方法了？

没有第一次想到，如果第一次做，我可能会用一个boolean[52]来check。（假设大小写都有）
但是在开始check之前要check输入的字符串长度小于等于52，不然直接返回false了

水逼一枚 发表于 2015-7-20 14:20
请问一下这个题你们是第一次做的时候就想到这个位运算的方法了？

这题我没用位运算啊，用32位整数来表示一个26元素的数组当然可以，不过我觉得水题上用这些技巧没必要。
我通常都是感到用数组会导致空间或效率问题时，才去用位运算来压缩。否则有点杀鸡用牛刀的感觉。
比如像这种题：http://poj.org/problem?id=1198
你要是不用位运算压缩状态的话，根本过不去。