（点击上方公众号，可快速关注）
来源：玻璃猫@伯乐在线专栏作者
链接：http://blog.jobbole.com/107689/
点击 → 了解如何加入专栏作者
小灰陷入了回忆当中……
题目：实现一个方法，判断一个正整数是否是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”的个数。要求性能尽可能高。
点击「阅读原文」，可和作者直接交流
专栏作者 （ 加入专栏作者 ）
玻璃猫：互联网公司的码农一枚，喜欢算法和面向对象设计。个人微信号：13522239721 ，个人订阅号：dreamsee321，欢迎一起交流讨论！
打赏支持作者写出更多好文章，谢谢
关注「算法爱好者」
看更多精选算法技术文章
↓↓↓
继续阅读
阅读原文