解題說明
Power of Four
題目描述：給定整數 n，判斷它是否是 4 的冪次方。4 的冪次方包含 1, 4, 16, 64, 256, ...
解題思路：4 的冪次方必須滿足三個條件：① n > 0；② n 是 2 的冪次方（即 (n & (n-1)) == 0，只有一個 1-bit）；③ 該唯一的 1-bit 必須落在奇數位（bit 0, 2, 4, 6, ...），可用掩碼 0x55555555（二進位為 01010101...）來驗證。同時滿足這三個條件即為 4 的冪次方。
C++ 解法
複雜度分析
時間複雜度：O(1) — 三個位元運算，常數時間完成。
空間複雜度：O(1) — 不使用額外空間。
虛擬碼
1. If n <= 0, return false 2. Check n is power of 2: (n & (n-1)) == 0 3. Check the single set bit is at an odd position: (n & 0x55555555) != 0 4. Return true only if all three conditions hold
其他解法
取對數法：計算 log(n) / log(4)，若結果為整數則是 4 的冪。但浮點精度問題可能導致錯誤。
遞迴法：若 n == 1 回傳 true；若 n % 4 != 0 回傳 false；否則遞迴呼叫 isPowerOfFour(n / 4)。邏輯直觀但有遞迴開銷。
模運算輔助：4 的冪次方模 3 餘 1（2 的奇數次方模 3 餘 2），因此可以用 isPowerOfTwo(n) && (n % 3 == 1) 代替掩碼檢查。
延伸思考
- 如何不使用迴圈、遞迴、對數，僅用 O(1) 的位元運算來解決？
- 如何判斷一個數是否為 8 的冪次方？掩碼應如何調整？
- 若 n 可以是負數，4 的冪次方的判斷邏輯是否需要改變？