呓语Beta 2.0 首页 镜头后 灶台前 捐赠者名单 有趣的小站

[说说位运算] 判断2的乘方

文档信息

前言

很久没有写技术博客了,今天看到一个有意思的位运算技巧,所以上来写写,这短短几句算作前言吧。

最为朴素的2的乘方判定方法

  1. 从2开始循环乘2,直到结果大于等于判定的数字为止
  2. 若结果和判定数字相等,则该数字为2的乘方
  3. 若结果最终超过了判定的数字,则该数字不为2的乘方

稍稍利用位运算提高效率

  1. 利用位运算的左移一位操作替代每次乘2的操作,在一定程度上提高效率,不过算法复杂度仍然是朴素算法的O(n)

利用位运算特点将复杂度降低至O(1)

  1. 所有2的乘方数字用二进制表示都是10…0形式,根据数字的大小位数不同。比如4就是100
  2. 所有2的乘方数字减一用二进制表示都是11…1形式,位数比2的乘方数少一位。比如4-1 = 3,3用二进制表示就是11
  3. 如果4和3按位与运算,结果就是0。所有的2的乘方和其-1的按位与运算结果都是0。
  4. 得出判断N是否为2的乘方的方法:N & (N-1) = 0 则N为2的乘方

付费支持

由于本网站没有广告和任何形式的收入来源,希望获得您的资助。每篇技术性文章和每期shellcasts视频定价人民币1元,在您付费后可以任意观看和下载。

可以使用支付宝手机钱包扫描下方的二维码进行付款操作或者用支付宝转帐给richard.ma.19850509@gmail.com,谢谢!

Fork me on GitHub