342. Power of Four

📘 題目敘述

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

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

條件限制

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

🧠 解題思路

延續之前的Power of Two，我把「4 的冪次方」拆成兩個條件一起檢查：

1) 先確定它是 2 的冪次方（只有一個 1-bit）

• n > 0：排除 0 與負數
• (n & (n - 1)) == 0：代表二進位中只有一個 bit 是 1 也就是 n 是 1, 2, 4, 8, 16, ... 這種 2 的冪

但這樣還不夠，因為 2^k 不一定是 4^x（例如 8 = 2^3 不是 4 的冪）。

2) 再確定那個 1-bit 在「偶數位」（才會是 4 的冪）

因為：

• 4^x = (2^2)^x = 2^(2x) 所以 4 的冪次方一定是 2 的偶數次方。

這份 code 用一個很常見的性質：

• 對任何 x >= 0，4^x % 3 == 1

所以用 (n % 3 == 1) 來排除掉像 2, 8, 32 這些「不是 4 的冪」的 2 冪數。

最後三個條件一起成立才回傳 true。

所有變數

• n：輸入整數

🪜 主要流程步驟

1. 排除 0 與負數

• n > 0

2. 用位元判斷是否為 2 的冪次方

• (n & (n - 1)) == 0

3. 用 % 3 == 1 篩出 4 的冪次方

• n % 3 == 1

4. 三個條件同時成立才回傳 true

• return n > 0 && ((n & (n - 1)) == 0) && (n % 3 == 1);

💻 程式碼實作

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

🔗 題目連結

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