位元操作 應用題 判斷輸入是否為2^k 二的冪 Leetcode 231: Power of Two

Possessed Photography on Unsplash

題目敘述

這題的題目會給我們一個輸入整數，要求我們判斷這個整數是否可以用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:

• -231 <= n <= 231 - 1

Follow up: Could you solve it without loops/recursion?

演算法

除了比較直覺的不斷除以二，判斷是否能剛好整除2的相除法之外。

class Solution:
　def isPowerOfTwo(self, n: int) -> bool:

　　while n > 1:
　　　if n % 2 != 0:
　　　　return False

　　　n /= 2

　　return n == 1

還有位元操作判斷法。

用n bitwiseAND (n-1) == 0 去判斷是否為2^n。
(這是因為2^k在二進位表達式中，只會有一個bit1出現)

2^k = 二進位的 100000..... 0

程式碼

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

複雜度分析

時間複雜度:

O( 1 ) 固定長度32bits的位元操作。

空間複雜度:

O(1) 都是固定尺寸的臨時變數，所占用的記憶體空間為常數級別。

關鍵知識點

聯想到2^k在二進位表達式中的規律為 10000...0 只會有一個bit 1出現

可以同步複習高度關聯的相似衍伸題 Power of four

Reference:

[1] Python/JS/Java/C++/Go O( 1 ) by bit-manipulation, [+ explanation ] - Power of Two - LeetCode