231. Power of Two

📘 題目敘述

給你一個整數 n，如果它是 2 的冪次方（power of two）就回傳 true，否則回傳 false。

如果存在一個整數 x 使得 n == 2^x，那麼 n 就是 2 的冪次方。

條件限制

• -2^31 <= n <= 2^31 - 1

🧠 解題思路（一）用位元且

看到topic後，我用位元運算 & 的性質判斷。

二的冪在二進位表示會長這樣：

• 1 -> 0001
• 2 -> 0010
• 4 -> 0100
• 8 -> 1000

也就是：只有一個 bit 是 1，其餘全部是 0。

如果 n 是二的冪，那 n - 1 會把那個唯一的 1 變成 0，並把右邊所有 bit 變成 1，所以：

• n & (n - 1) 一定會變成 0

反過來，如果 n 不是二的冪，代表至少有兩個 bit 是 1，那 n & (n - 1) 就不會是 0。

另外 n 必須是正數，因為 0 或負數都不可能是 2^x。

所有變數

• n：輸入整數

🪜 主要流程步驟

1. 先排除不可能的輸入

• 若 n <= 0，直接回傳 false

2. 用位元且判斷是否只有一個 1-bit

• 計算 (n & (n - 1))
• 若結果等於 0，回傳 true，否則回傳 false

💻 程式碼實作（一）位元且版本

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

🧠 解題思路（二）直覺解法，但速度慢

我的想法是：如果 n 真的是 2^x，那它一定可以一直被 2 整除，最後會變成 1。

所以流程很直觀：

• 只要 n 還能被 2 整除，而且 n > 1：
  • 就把 n /= 2（把一個 2 的因子剝掉）
• 如果某一刻 n == 1：
  • 代表剛好除到 2^0，回傳 true
• 其他情況：
  • 代表中途卡住（不能再整除）或一開始就不可能（例如 n <= 0），回傳 false

所有變數

• n：目前要檢查的數字（會在迴圈中一路被除以 2）

🪜 主要流程步驟

1. 持續把 n 除以 2（只在「還能整除且還沒到 1」時）

• 條件是：
  • n % 2 == 0
  • 且 n > 1
• 滿足就做：
  • n /= 2

2. 如果 n 變成 1，代表是 2 的冪次方

• n == 1 → true

3. 其他任何情況都不是

• 例如：
  • 中途出現 n % 2 != 0
  • 或者一開始 n <= 0
  • 或者 n 變成 3、-1 之類不可能回到 1 的值
• 直接回傳 false

💻 程式碼實作（二）while解法

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

🔗 題目連結

https://leetcode.com/problems/power-of-two/