#6 判断一个数是否为2的n次方

发布时间:2019-02-23 15:12  浏览次数:88

「ALBB面试题」

【题目】

如何判断一个数是否为2的n次方

【题目分析】


看到这种题,相信大家第一反应就是循环除2,这样做肯定是可以得出结果的;但是这种做法无疑大大增加了计算机的运行时间,一个非常大的数字可能会让计算机内存溢出,有没有更好的解决方式呢?有!如果你对数字2敏感,那么一定会想到二进制方法,2
0=0b1、21=10、22=0b100、23
=0b1000......通过找规律发现,只要是2的n次方,它的二进制表示形式中1只有一个。所以本题转换为判断一个数字的二进制形式中1是否只有一个。那么该如何统计呢?

方法一:将其转换为字符串,之后统计1的个数

方法二:再仔细观察,20-1=0、21-1=0b01、22-1=0b011、23-1=0b0111......,得到规律:如果一个数字i为2的n次方,则 
i&(i-1)=0 (推荐)

【解答】

方法一:
1 #!/Users/minutesheep/.pyenv/shims/python 2 # -*- coding: utf-8 -*- 3 4 5
def isPower(n): 6 ''' 7 判断是否为2的n次方 8 ''' 9 try: 10 n = str(bin(n)) 11 if
n.count('1') == 1: 12 return print('是2的n次方') 13 return print('不是2的n次方') 14
except: 15 return print('错误:只接收数字') 16 17 18 if __name__ == '__main__': 19
test_num = 204820 isPower(test_num) 程序源代码 是2的n次方 运行结果
方法二:
1 #!/Users/minutesheep/.pyenv/shims/python 2 # -*- coding: utf-8 -*- 3 4 5
def isPower(n): 6 ''' 7 判断是否为2的n次方 8 ''' 9 try: 10 if n&(n-1) == 0: 11
return print('是2的n次方') 12 return print('不是2的n次方') 13 except: 14 return print('
错误:只接收数字') 15 16 17 if __name__ == '__main__': 18 test_num = 2048 19
isPower(test_num) 程序源代码 是2的n次方 运行结果

标签

归档

阅读排行