如何判读一个整数是否是2的整数次幂(三种方法实现)

一、题目
二、解题方法
1、方法一
2、方法二
3、方法三

一、题目

实现一个方法，判断一个正数是否是2的整数次幂。(如：8是2的3次幂，返回True，9不是，返回False)要求性能尽可能地高。

二、解题方法

1、方法一

暴力解法：设置一个中间量temp=1，每次乘以2后和原数据比较，如果等于则返回True，否则继续乘2。直到大于原数据，返回False。
时间复杂度为O(logn)

代码实现：

def is_power_of_2(num):
    temp=1
    while temp<=num:
        if temp==num:
            return True
        else:
            temp *= 2
    return False

print(is_power_of_2(8))
print(is_power_of_2(9))

2、方法二

与方法一相同，只是把temp*2变成了temp向左移1位。（移位运算效率比较高）
这种方法其实并没有实质性的提高效率，时间复杂度仍然为O(logn)

代码实现：

def is_power_of_2(num):
    temp=1
    while temp<=num:
        if temp==num:
            return True
        else:
            temp=temp << 1
    return False

print(is_power_of_2(8))
print(is_power_of_2(9))

3、方法三

我们可以把数据转化为二进制数来找寻特征：
不管是2的任何次幂，其二进制形式都是 1XXXXXX，只有最高为位为1，其他位全为0
在此基础上，把原数据减1，就变成了 111111 的形式，二进制数字全变成了1。
这个时候，我们让 n&(n-1),其结果必然为0 。

所以。判断一个数是否是2的整数次幂，就看是否满足: n&(n-1)==0,满足即是2的整数次幂，反之则不是。
该方法的时间复杂度为O(1) 。

代码实现：

def is_power_of_2(num):
    return num&(num-1)==0

print(is_power_of_2(8))
print(is_power_of_2(9))