📏二進位操作 Power of 2_n是否為2的k次方_Leetcode #231

Possessed Photography on Unsplash

題目敘述

題目會給定一個輸入整數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會恰好等於零。

利用這個特質來做判斷。

Refernce:

[1] Power of Two - LeetCode