#6 判斷一個數是否為2的n次方
「ALBB面試題」
【題目】
如何判斷一個數是否為2的n次方
【題目分析】
看到這種題,相信大家第一反應就是迴圈除2,這樣做肯定是可以得出結果的;但是這種做法無疑大大增加了計算機的執行時間,一個非常大的數字可能會讓計算機記憶體溢位,有沒有更好的解決方式呢?有!如果你對數字2敏感,那麼一定會想到二進位制方法,20 =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''' 9try: 10n = str(bin(n)) 11if n.count('1') == 1: 12return print('是2的n次方') 13return print('不是2的n次方') 14except: 15return print('錯誤:只接收數字') 16 17 18 if __name__ == '__main__': 19test_num = 2048 20isPower(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''' 9try: 10if n&(n-1) == 0: 11return print('是2的n次方') 12return print('不是2的n次方') 13except: 14return print('錯誤:只接收數字') 15 16 17 if __name__ == '__main__': 18test_num = 2048 19isPower(test_num) 程式原始碼
是2的n次方 執行結果