实现一个方法，判断一个正整数是否是2的乘方（比如16是2的4次方，返回True；否则返回False）
方法一：使用该数循环除以2，如果最终商是1并且余数是0，则返回True；循环中一旦出现余数不为0，则返回False
方法二：从1开始循环乘以2，直到结果第一次大于或者等于目标值，如果相等，则放回True，如果大于，则返回False
方法三：借助位运算
如果该数是2的乘方，则该数的二进制表示仅包含一个1，那么该数与他的减一的数相与，一定为0； 否则该数一定不是2的乘方。
以数字5为例： 0000 0101 & 0000 0100 = 0000 0100
以数字8为例 ：0000 1000 & 0000 0111 = 0000 0000
与方法一二比较，通过该方法只需要一次运算即可得出结果
Python代码及耗时统计如下：
#!/usr/bin/python
#-*- coding:utf-8 -*-
import time
def isPowerOf2_1(i):
if i < 1:
return False
while i > 1:
if(i % 2):
return False
i = i / 2
return True
def isPowerOf2_2(i):
j = 1
while j < i:
j = j * 2
if j == i:
return True
return False
def isPowerOf2_3(i):
if i < 1:
return False
if(i & (i - 1)):
return False
return True
def computeNum1(i):
num = 0
while(i):
num += 1
i = i & (i - 1)
return num
if __name__ == "__main__":
num = 20000000
lst1 = list()
start = time.time()
for i in range(num):
if (isPowerOf2_1(i)):
lst1.append(i)
end = time.time()
print "used time: %s" % (end - start), lst1
lst2 = list()
start = time.time()
for i in range(num):
if (isPowerOf2_2(i)):
lst2.append(i)
end = time.time()
print "used time: %s" % (end - start), lst2
lst3 = list()
start = time.time()
for i in range(num):
if (isPowerOf2_3(i)):
lst3.append(i)
end = time.time()
print "used time: %s" % (end - start), lst3
print computeNum1(142)
print computeNum1(143)
print computeNum1(128)
运行结果
used time: 12.3350000381 [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216]
used time: 46.5840001106 [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216]
used time: 7.85400009155 [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216]
4
5
1
Process finished with exit code 0
拓展： 如何计算一个正整数的二进制表示含有多少个1？
借助方法三，一个正整数N与N-1相与的结果是1的个数减一，那么我们可以不断的相与直至结果为0，就可以统计1的个数了
142的二进制表示为1000 1110 共4个1
第一次相与减少一个1： 1000 1110 & 10001101 = 1000 1100 N更新为1000 1100，3个1
第二次相与减少一个1： 1000 1100 & 1000 1011 = 1000 1000 N更新为1000 1000，2个1
第三次相与减少一个1： 1000 1000 & 1000 0111 = 1000 0000 N更新为1000 0000，1个1
第四次相与减少一个1： 1000 0000 & 0111 1111 = 0000 0000 N更新为 0000 0000，0个1
四次相与后，变为0，说明142有4个1
代码实现在上面代码里函数computeNum1里
