題目敘述
題目會給定一個輸入整數n，要求我們判斷n是不是恰好為2的k次方的正整數?
題目的原文敘述測試範例
Example 1:
Input: n = 1
Output: true
Explanation: 20 = 1
Example 2:
Input: n = 16
Output: true
Explanation: 24 = 16
Example 3:
Input: n = 3
Output: false
約束條件
Constraints:
-2^31 <= n <= 2^31 - 1
n 介於32bits 整數範圍之內。
Follow up: Could you solve it without loops/recursion?
請問您能不能不要依賴迴圈或者遞回解出來這題?
演算法 二進位操作
除了第一直覺不斷除以二的模擬法，藉由最後能不能整除2來判斷以外，其實還有一個更高效率的二進位判斷法。
我們知道，所有的2^k正整數都可以寫成這個形式
2^ k = 二進位的 1 0 .....0 0
那麼
2^k - 1 就是二進位的 0 1 .....1 1
----------------------------------------
兩者做bitwise AND 會恰好等於零。
因此，我們可以說，如果n是2^k正整數，那麼n bitwise AND (n-1) 必定等於 0。
如果不滿足，那麼n就一定不是2^k的正整數。
程式碼 二進位操作
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
if n <= 0:
return False
# note:
# power of 2 in binary = b' 1000 ... 0
# power of 2 minus 1 in binary = b' 0111 ... 1
# bitwise AND of n and (n-1) must be 0 if n is power of 2
return ( n & ( n-1 ) ) == 0
複雜度分析 二進位操作
時間複雜度:
如果n無不限制範圍，那麼所需時間為位元寬度 = O( log n )
題目已經說是32bit的整數範圍內，可視為一次性的常數操作，所需時間為O(1)。
空間複雜度:
所用到的都是固定尺寸的臨時變數，所需空間為O(1)常數級別。
關鍵知識點
由n=2^k正整數的二進位規律，發現n和n-1做bitwise AND會恰好等於零。
利用這個特質來做判斷。
