漫画:判断2的乘方

1 2 3 4

小灰陷入了回忆当中……

5 6 7

题目:实现一个方法,判断一个正整数是否是2的乘方(比如16是2的4次方,返回True;18不是2的乘方,返回False)。要求性能尽可能高。

8 9

解法一:

创建一个中间变量Temp,初始值是1。然后进入一个循环,循环中每次让Temp和目标整数比较,如果相等,则说明目标整数是2的乘方;如果不相等,则让Temp增大一倍,继续循环比较。当Temp大于目标整数时,说明目标整数不是2的乘方。

如果目标整数的大小是N,则此方法的时间复杂度是O(LogN)。

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

解法二:

非常有趣也非常简单的解法。因为2的乘方都符合一个规律,即 N&N-1 等于 0,所以直接用这个规律判断即可。该算法时间复杂度是O(1)。

33 34 35

思考题:

实现一个方法,求出一个正整数转换成二进制后的数字“1”的个数。要求性能尽可能高。

36

打赏支持我写出更多好文章,谢谢!

打赏作者

打赏支持我写出更多好文章,谢谢!

3 12 收藏 19 评论

关于作者:玻璃猫

互联网公司的码农一枚,喜欢算法和面向对象设计。个人微信号:18910791086微信公众号:程序员小灰(chengxuyuanxiaohui)欢迎一起交流讨论! 个人主页 · 我的文章 · 100 ·  

可能感兴趣的话题



直接登录
最新评论
  • fengvs   2016/11/13

    依次计算n&n-1,个数+1
    不为0则继续

  • 贵在线选了个便宜又业余的云放图吗?

    整篇图全部挂了,漫画。。。

    http://jbcdn2.b0.upaiyun.com/2016/11/f87aab3cd691f6caacc336af7f32988d.jpg

    访问 upaiyun.com 看到熟悉的
    Welcome to nginx!

  • 摔死的猫katty   2016/11/14

    又学习了

  • Sun_1956 90后程序猿 2016/11/14

     

    • cologler   2016/11/14

      你理解就聊你怎么理解的就好了,扔一份别人的源码在这里有什么用?

      举个例子:你去面试的似乎别人问你一个排序算法,然后你当场掏出手机搜索出这个算法的实现告诉面试官:“别人都写好了,我干嘛还要重写写一遍?”。

      • Sun_1956 90后程序猿 2016/11/14

        你用的算法难道不是别人写出来的,什么思想,我只是告诉这里,还有更优的实现

        • cologler   2016/11/15

          没有面试官要求你去发明一个排序算法吧?那为什么别人要考呢?几乎每个语言都实现了全部的排序算法吧?为什么要问算法的实现而不问你能去哪找到这个排序算法呢?为什么不能直接用呢?为什么不干脆抱着打印好的每个算法的实现去面试?

          为什么网络上对同样一个算法却要描述这么多次?为什么在 google 上搜索快速排序就有 140W 以上结果?难道有人发明了这么多遍?

          每个人对一个算法的理解程度不同,所以每个人的描述都不一样。因为觉得自己描述的比别人描述的更容易理解,所以大家才一遍又一遍用自己的理解来描述原理明明一样的算法。

        • cologler   2016/11/15

          你不理解你上面的算法,给你个 uint 或 long 的参数你怎么实现?无限长的 bigint 呢?

          不理解算法原理,你根本不清楚适用于什么范围。

      • ★小V★ 程序員 2016/11/14

        但至少你要知道怎麼寫把?如果人家給張紙說,我們把merge sort寫一下,你就告訴人家怎麼理解麼?

        • cologler   2016/11/15

          既然网上都有全部算法的实现,为什么不能当场掏出手机来抄?既然觉得抄代码实现算法慢,为什么不能直接复制粘贴?你为什么觉得把算法默写下来就算你了解这个算法了?算法本来就是脱离编程语言的,不管你用口语实现还是用编程语言实现,都是为了表现你能理解这个算法,展现的是你的理解和应用能力。

          考算法是考人,不是真的考算法,算法是不变的,人才是可变的。

  • cologler   2016/11/14

    “因为 2 的乘方都符合一个规律,即 N & N-1 等于 0。”

    这只是必要性,还没证明充分性吧。

    • 玻璃猫 程序员 2016/11/18

      你说的有道理。我刚才思索了一下,觉得可以利用反证法证明:

      假设真的存在一个正整数N,N不是2的幂,但是N符合N&N-1 =0。

      由N不是2的幂可以推断出,N的二进制形式并不是除了最高位是1以外,其余为全是0。

      既然其余位不全是0,那么N-1的结果的最高位一定不会改变,仍然是1。

      既然N-1的最高位是1,N的最高位也是1,那么N&N-1 !=0,和假设矛盾。

      由此证明,符合N&N-1 =0的正整数必然是2的幂。

  • 图形理解更符合学习啊

  • 类似二分法查找把这个值循环按照二分法得到的值除以2,如果能整除说明是2的乘方,否则不是。自己临时想的一个,应该也可以吧,回去写段代码试验下

  • 用log2() ,来判断,结果为整数也可以把

  • 经典计算机结构下,基础算法已经穷尽。我们要做的是组合。除非你是新领域的开天辟地者~

跳到底部
返回顶部