一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 594|回复: 11
收起左侧

[编程题] 简单的位运算,但是不懂原理

[复制链接] |试试Instant~ |关注本帖
神罗天征 发表于 2015-7-19 23:09:56 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
在看判断一个字符串中的字符是否唯一(只用基本数据结构)的程序中,发现它用了位运算来求解,自己动手算了一下,但是自己对于位运算接触的太少,不解其中的原理,请教各位,程序里左移是为什么呢?这个程序的基本思想是什么呀?谢谢!
  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.   }
复制代码

评分

1

查看全部评分

rogerdai 发表于 2015-7-19 23:19:58 | 显示全部楼层
这是用每一个bit对应字符. 如果出现过,那么checker上这个bit就为1,不然就是0. 这里应该是假设所有输入都只有小写字符,不然31个bit装不下48个字符
回复 支持 反对

使用道具 举报

 楼主| 神罗天征 发表于 2015-7-19 23:26:12 | 显示全部楼层
rogerdai 发表于 2015-7-19 23:19
这是用每一个bit对应字符. 如果出现过,那么checker上这个bit就为1,不然就是0. 这里应该是假设所有输入都 ...

恍然大悟啊,它确实假设了只有小写字母,谢谢!
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-20 00:49:03 | 显示全部楼层
位运算很好玩,习惯了以后你会喜欢的~~
回复 支持 反对

使用道具 举报

水逼一枚 发表于 2015-7-20 14:20:25 | 显示全部楼层
zhuli19901106 发表于 2015-7-20 00:49
位运算很好玩,习惯了以后你会喜欢的~~

请问一下这个题你们是第一次做的时候就想到这个位运算的方法了?
回复 支持 反对

使用道具 举报

水逼一枚 发表于 2015-7-20 14:20:39 | 显示全部楼层
rogerdai 发表于 2015-7-19 23:19
这是用每一个bit对应字符. 如果出现过,那么checker上这个bit就为1,不然就是0. 这里应该是假设所有输入都 ...

请问一下这个题你们是第一次做的时候就想到这个位运算的方法了?
回复 支持 反对

使用道具 举报

rogerdai 发表于 2015-7-20 15:10:40 | 显示全部楼层
水逼一枚 发表于 2015-7-20 14:20
请问一下这个题你们是第一次做的时候就想到这个位运算的方法了?

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

使用道具 举报

zhuli19901106 发表于 2015-7-20 16:35:04 | 显示全部楼层
水逼一枚 发表于 2015-7-20 14:20
请问一下这个题你们是第一次做的时候就想到这个位运算的方法了?

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

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 11:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表