document.write('
方法一:构造法
2的n次方可以表示为:20,21,22…,2n,如果一个数是2的n次方,那么最直观的想法是对1执
行了移位操作(每次左移一位),即通过移位得到的值必定是2的n次方(针对n的所有取值构造出所有
可能的值)。所以要想判断一个数是否为2的n次方,只需要判断该数移位后的值是否与给定的数相
等,实现代码如下:
#判断n能否表示成2的n次方
def isPower(n):
if n<1:
return False
i=1
while i<=n:
if i==n:
return True
i<<=1
return False
if __name__==\'_main__":
if isPower(8):
print "8能表示成2的n次方"
else:
print "8不能表示成2的n次方"
if isPower(9):
print "9能表示成2的n次方"
else:
print "9不能表示成2的n次方"
程序的运行结果为:
8能表示成2的n次方
9不能表示成2的n次方
算法性能分析:
上述算法的时间复杂度为O(logn)。
方法二:与操作法
那么是否存在效率更高的算法昵?通过对20,21,22…,2n进行分析,发现这些数字的二进制形式
分别为:1,10,100,…。从二进制的表示可以看出,如果一个数是2的n次方,那么这个数对应的
二进制表示中有且只有一位是1,其余位都为0。因此判断一个数是否为2的n次方可以转换为这个数
对应的二进制表示中是否只有一位为1。如果一个数的二进制表示中只有一位是1,例如
num=00010000,那么num-1的二进制表示为num-1=00001111,由于num与num-1二进制表
示中每一位都不相同,因此num&(num-1)的运算结果为0。可以利用这种方法来判断一个数是否为
2的n次方。实现代码如下:
def isPower(n):
if n<1:
return False
m=n&(n-1)
return m==0
算法性能分析:
这种方法的时间复杂度为O(1)。
');