微信号:programmer_club

介绍:程序员第一自媒体,与你探讨码农人生路上遇到的各类泛技术话题,定期为你推荐码农人生思考、感悟以及启迪!

漫画算法:判断2的乘方

2016-11-05 22:02 玻璃猫










小灰陷入了回忆当中......









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









解法一:


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


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




































小灰的回忆到此结束......





































解法二:


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











思考题:


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






—————END—————



来源于:伯乐在线 - 玻璃猫 

关注作者,获取更多内容

作者个人微信号:13522239721

让大神带你飞!!!


 
程序员之家 更多文章 你的第一门编程语言 容器集群管理平台哪个最好? 缓存cache?什么鬼? 爱情代码专题(一) 学好安卓,你需要知道些什么?
猜您喜欢 棱安全送福利 · 乌云白帽大会 WHF · 2016 门票免费赠送 Linux的进程间通信-消息队列 长庆油田年产油气当量突破5500万吨 Java日志框架研究及常见配置 DockerCon 2016 D2|剑指商业化