LeetCode 231：2 的冪次方判定 - 位運算與迭代雙解法

問題描述

給定一個整數，編寫函數判斷其是否為 2 的冪次方（即 2^k, k ≥ 0）。

方法一：位運算（最優解）

核心性質：2 的冪次方在二進制中只有最高位為 1，其餘為 0（如 8 = 1000₂）。n-1 則是最高位變 0，其餘變 1（7 = 0111₂）。因此 n & (n-1) == 0 可判斷是否為 2 的冪次方。

class Solution {
public:
    bool isPowerOfTwo(int n) {
        if (n <= 0) return false;
        return (n & (n - 1)) == 0;
    }
};

方法二：迭代除以 2

不斷除以 2，若過程中出現餘數非 0 且商不為 1，則非 2 的冪次方。

class Solution {
public:
    bool isPowerOfTwo(int n) {
        if (n <= 0) return false;
        while (n > 1) {
            if (n % 2 != 0) return false;
            n /= 2;
        }
        return true;
    }
};

方法三：數學性質（整數範圍內）

32 位有號整數最大的 2 的冪次方為 2^30 = 1073741824。若 n > 0 且 1073741824 % n == 0，則 n 為 2 的冪次方。

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && 1073741824 % n == 0;
    }
};

複雜度分析

測試範例

• 1 (2^0) → true
• 16 (2^4) → true
• 3 → false
• 0 → false
• -16 → false