## 題目地址(342. 4的冪) https://leetcode-cn.com/problems/power-of-four/ ## 題目描述 > 給定一個整數 (32 位有符號整數)，請編寫一個函數來判斷它是否是 4?的冪次方。 示例 1: 輸入: 16 輸出: true 示例 2: 輸入: 5 輸出: false 進階： 你能不使用循環或者遞歸來完成本題嗎？ ## 前置知識 - 數論 ## 公司 - 百度 - twosigma ## 思路 符合直覺的做法是不停除以 4 直到不能整除，然后判斷是否為 1 即可。 代碼如下： ```js while (num && num % 4 == 0) { num /= 4; } return num == 1; ``` 但是這道題目有一個 follow up: “你是否可以不使用循環/遞歸完成”。因此我們需要換種思路。 我們先來看下，4 的冪次方用 2 進制表示是什么樣的.  發現規律： 4 的冪次方的二進制表示 1 的位置都是在奇數位（且不在最低位），其他位置都為 0 我們還可以發現： 2 的冪次方的特點是最低位之外，其他位置有且僅有一個 1（1 可以在任意位置） 我們進一步分析，如果一個數字是四的冪次方，那么只需要滿足： 1. 是 2 的冪次方， 就能保證最低位之外，其他位置有且僅有一個 1 2. 這個 1 不在偶數位置，一定在奇數位置 對于第一點，如果保證一個數字是 2 的冪次方呢？ 顯然不能不停除以 2，看結果是否等于 1，這樣就循環了。 我們可以使用一個 trick， 如果一個數字 n 是 2 的冪次方，那么 n & (n - 1) 一定等于 0， 這個可以作為思考題，大家思考一下。 對于第二點，我們可以取一個特殊數字，這個特殊數字，奇數位置都是 1，偶數位置都是 0，然后和這個特殊數字 `求與`， 如果等于本身，那么毫無疑問，這個 1 不再偶數位置，一定在奇數位置，因為如果在偶數位置，`求與`的結果就是 0 了 題目要求 n 是 32 位有符號整形，那么我們的特殊數字就應該是`01010101010101010101010101010101`(不用數了，一共 32 位)。  如上圖，64和這個特殊數字求與，得到的是本身。 8 是 2的次方，但是不是4的次方，我們求與結果就是0了。 為了體現自己的逼格，我們可以使用計算器，來找一個逼格比較高的數字，這里我選了十六進制，結果是`0x55555555`。  代碼見下方代碼區。 說實話，這種做法不容易想到，其實還有一種方法。 如果一個數字是 4 的冪次方，那么只需要滿足： 1. 是二的倍數 2. 減去 1 是三的倍數 代碼如下： ```js return num > 0 && (num & (num - 1)) === 0 && (num - 1) % 3 === 0; ``` ## 關鍵點 - 數論 - 2的冪次方特點（數學性質以及二進制表示） - 4的冪次方特點（數學性質以及二進制表示） ## 代碼 語言支持：JS, Python JavaScript Code： ```js /* * @lc app=leetcode id=342 lang=javascript * * [342] Power of Four */ /** * @param {number} num * @return {boolean} */ var isPowerOfFour = function(num) { // tag: 數論 if (num === 1) return true; if (num < 4) return false; if ((num & (num - 1)) !== 0) return false; return (num & 0x55555555) === num; }; ``` Python Code: ```python class Solution: def isPowerOfFour(self, num: int) -> bool: if num == 1: return True elif num < 4: return False else: if not num & (num-1) == 0: return False else: return num & 0x55555555 == num # 另一種解法：將數字轉化為二進制表示的字符串，利用字符串的相關操作進行判斷 def isPowerOfFour(self, num: int) -> bool: binary_num = bin(num)[2:] return binary_num.strip('0') == '1' and len(binary_num) % 2 == 1 ``` **復雜度分析** - 時間復雜度：$O(1)$ - 空間復雜度：$O(1)$ 更多題解可以訪問我的LeetCode題解倉庫：https://github.com/azl397985856/leetcode 。 目前已經37K star啦。 關注公眾號力扣加加，努力用清晰直白的語言還原解題思路，并且有大量圖解，手把手教你識別套路，高效刷題。