算法趣谈—漫画：判断 2 的乘方－算法学习不再枯燥

来源：玻璃猫

链接：http://blog.jobbole.com/107689/

小灰陷入了回忆当中……

题目：实现一个方法，判断一个正整数是否是2的乘方（比如16是2的4次方，返回True；18不是2的乘方，返回False）。要求性能尽可能高。

解法一：

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

如果目标整数的大小是N，则此方法的时间复杂度是O（LogN）。

解法二：

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

思考题：

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

关于Java和Android大牛频道

Java和Android大牛频道是一个数万人关注的探讨Java和Android开发的公众号，分享和原创最有价值的干货文章，让你成为这方面的大牛！

我们探讨android和Java开发最前沿的技术：android性能优化 ，插件化，跨平台，动态化，加固和反破解等，也讨论设计模式／软件架构等。由一群来自BAT的工程师组成的团队。

关注即送红包，回复：“百度” 、“阿里”、“腾讯” 有惊喜！！！关注后可用入微信群。群里都是来自百度阿里腾讯的大牛。

欢迎关注我们，一起讨论技术，扫描和长按下方的二维码可快速关注我们。或搜索微信公众号:JANiubility。

公众号：JANiubility