漫画算法:判断2的乘方

漫画算法:判断2的乘方



漫画算法:判断2的乘方



漫画算法:判断2的乘方



漫画算法:判断2的乘方



小灰陷入了回忆当中……



漫画算法:判断2的乘方



漫画算法:判断2的乘方


漫画算法:判断2的乘方



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



漫画算法:判断2的乘方



漫画算法:判断2的乘方



解法一:


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


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



漫画算法:判断2的乘方



漫画算法:判断2的乘方


漫画算法:判断2的乘方



漫画算法:判断2的乘方



漫画算法:判断2的乘方



漫画算法:判断2的乘方


漫画算法:判断2的乘方



漫画算法:判断2的乘方



漫画算法:判断2的乘方



漫画算法:判断2的乘方



漫画算法:判断2的乘方



小灰的回忆到此结束……



漫画算法:判断2的乘方



漫画算法:判断2的乘方



漫画算法:判断2的乘方



漫画算法:判断2的乘方



漫画算法:判断2的乘方



漫画算法:判断2的乘方



漫画算法:判断2的乘方



漫画算法:判断2的乘方



漫画算法:判断2的乘方



漫画算法:判断2的乘方



漫画算法:判断2的乘方



漫画算法:判断2的乘方



漫画算法:判断2的乘方



漫画算法:判断2的乘方



解法二:


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


漫画算法:判断2的乘方


漫画算法:判断2的乘方



漫画算法:判断2的乘方



思考题:


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



漫画算法:判断2的乘方



—————END—————






喜欢本文的朋友们,欢迎长按下图关注订阅号梦见,收看更多精彩内容

漫画算法:判断2的乘方



原文始发于微信公众号(程序员小灰):漫画算法:判断2的乘方

本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 漫画算法:判断2的乘方

我还会在以下平台发布内容

GitHub 哔哩哔哩