探索之旅:位运算

分享到:  QQ好友和群QQ好友和群 QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友 微信微信
查看查看253 回复回复2 收藏收藏 分享淘帖 转播转播 分享分享 微信
查看: 253|回复: 2
收起左侧

探索之旅:位运算

[复制链接]
Ding 发表于 2016-11-3 18:25:55 | 显示全部楼层 |阅读模式
快来登录
获取最新的苹果动态资讯
收藏热门的iOS等技术干货
拷贝下载Swift Demo源代码
本帖最后由 Ding 于 2016-11-4 18:12 编辑

大题小作一下,明天准备看看并分享BitSet的实现,所以先来个关于位运算的小问题热热身。

探索之旅:位运算 2

探索之旅:位运算 - 敏捷大拇指 - 探索之旅:位运算 2


这个问题是去年某个QQ群里的小伙伴问的,很有趣:

给定一个整数n,怎么写出它关于2的幂的和的表达式?

即实现这样一个函数:

[Swift] 纯文本查看 复制代码
func f2(_ n: UInt) -> String


能够达到这样的效果:

[Swift] 纯文本查看 复制代码
var s = f2(15)  // "15=2^0+2^1+2^2+2^3"

s = f2(11)      // "11=2^0+2^1+2^3"

s = f2(64000000)// "64000000=2^12+2^15+2^20+2^22+2^23+2^24+2^25"

s = f2(1024)    // "1024=2^10"


有兴趣的同学可以发表下自己的实现,语言不限。稍后附上自己的思路和代码。

(过了一段时间...)

这个问题主要是为《数据结构:BitSet》热身用的,如今BitSet已经写成,是时候说说自的思路了:

如果从计算机的角度来看这个问题就会变得非常简单。

比如数字5,在计算机看来就是:

0...00000000000101

我们定义从右往左依次为第0位、第1位、第2位...

可见,5的第0位和第2位是1,其他位都是0,所以5就是2的0次方加上2的2次方:

5=2^0+2^2

再来看数字1024,二进制就是:

0...00000010000000000

所以:

1024=2^10

明白了这些,代码就水到渠成了:

[Swift] 纯文本查看 复制代码
func f2(_ n: UInt) -> String {
    
    guard n > 0 else { return "0=0" }
    
    var s = "\(n)="
    var number = n
    var count = 0
    
    while number != 0 {
        if number & 1 == 1 {    //可以写成 if number % 2 == 1
            s += "2^\(count)+"
        }
        count += 1
        number >>= 1            //可以写成 number /= 2
    }
    s.remove(at: s.index(before: s.endIndex))
    
    return s
}



刚翻译完国际友人Matthijs Hollemans的链表实现文档,他写得实在是太翔实,都有点啰嗦了。编程还是要自己多悟的,别人说再多,没悟的话都是干扰。上边的代码就不多说了。

值得注意的是注释,有小伙伴留言说这个问题貌似要用辗转相除,嗯,确实是这样。不过要是把判断number的最后一位是不是1写成与运算而不是判断是不是奇数更好理解,也更有效率;同样,把number右移一位写成 number >>= 1 也远比 number /= 2 来的直观且高效。

周末愉快~




探索之旅:位运算 1

探索之旅:位运算 - 敏捷大拇指 - 探索之旅:位运算 1














都看到这里了,就把这篇资料推荐给您的好朋友吧,让他们也感受一下。

回帖是一种美德,也是对楼主发帖的尊重和支持。

*声明:敏捷大拇指是全球最大的Swift开发者社区、苹果粉丝家园、智能移动门户,所载内容仅限于传递更多最新信息,并不意味赞同其观点或证实其描述;内容仅供参考,并非绝对正确的建议。本站不对上述信息的真实性、合法性、完整性做出保证;转载请注明来源并加上本站链接,敏捷大拇指将保留所有法律权益。如有疑问或建议,邮件至marketing@swifthumb.com

*联系:微信公众平台:“swifthumb” / 腾讯微博:@swifthumb / 新浪微博:@swifthumb / 官方QQ一群:343549891(满) / 官方QQ二群:245285613 ,需要报上用户名才会被同意进群,请先注册敏捷大拇指

嗯,不错!期待更多好内容,支持一把:
支持敏捷大拇指,用支付宝支付10.24元 支持敏捷大拇指,用微信支付10.24元

评分

参与人数 1金钱 +10 贡献 +10 专家分 +10 收起 理由
Anewczs + 10 + 10 + 10 32个赞!专家给力!

查看全部评分

本帖被以下淘专辑推荐:

3rdev 发表于 2016-11-3 21:25:54 | 显示全部楼层
记得是什么辗转相除吧
 楼主| Ding 发表于 2016-11-4 08:00:55 | 显示全部楼层
3rdev 发表于 2016-11-3 21:25
记得是什么辗转相除吧

哈哈,是的。只不过我是把除法改成了右移,取模改成了与。站在计算机的角度,这样更好理解,也更高效。
过一段时间我会详解一把。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

做任务,领红包。
我要发帖

分享扩散

都看到这里了,就把这资料推荐给您的好朋友吧,让他们也感受一下。
您的每一位朋友访问此永久链接后,您都将获得相应的金钱积分奖励
热门推荐

合作伙伴

Swift小苹果

  • 北京治世天下科技有限公司
  • ©2014-2016 敏捷大拇指
  • 京ICP备14029482号
  • Powered by Discuz! X3.1 Licensed
  • swifthumb Wechat Code
  •   
快速回复 返回顶部 返回列表