# 0342. 4的冪 ## 題目地址(342. 4的冪) <https://leetcode-cn.com/problems/power-of-four/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個整數 (32 位有符號整數)，請編寫一個函數來判斷它是否是 4 的冪次方。 示例 1: 輸入: 16 輸出: true 示例 2: 輸入: 5 輸出: false 進階： 你能不使用循環或者遞歸來完成本題嗎？ ``` ``` ## 前置知識 - 數論 ## 公司 - 百度 - twosigma ## 思路 符合直覺的做法是不停除以 4 直到不能整除，然后判斷是否為 1 即可。 代碼如下： ``` <pre class="calibre18">``` <span class="hljs-keyword">while</span> (num && num % <span class="hljs-params">4</span> == <span class="hljs-params">0</span>) { num /= <span class="hljs-params">4</span>; } <span class="hljs-keyword">return</span> num == <span class="hljs-params">1</span>; ``` ``` 但是這道題目有一個 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 是三的倍數 代碼如下： ``` <pre class="calibre18">``` <span class="hljs-keyword">return</span> num > <span class="hljs-params">0</span> && (num & (num - <span class="hljs-params">1</span>)) === <span class="hljs-params">0</span> && (num - <span class="hljs-params">1</span>) % <span class="hljs-params">3</span> === <span class="hljs-params">0</span>; ``` ``` ## 關鍵點 - 數論 - 2的冪次方特點（數學性質以及二進制表示） - 4的冪次方特點（數學性質以及二進制表示） ## 代碼 語言支持：JS, Python JavaScript Code： ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=342 lang=javascript * * [342] Power of Four */</span> <span class="hljs-title">/** * @param {number} num * @return {boolean} */</span> <span class="hljs-keyword">var</span> isPowerOfFour = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">num</span>) </span>{ <span class="hljs-title">// tag: 數論</span> <span class="hljs-keyword">if</span> (num === <span class="hljs-params">1</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">true</span>; <span class="hljs-keyword">if</span> (num < <span class="hljs-params">4</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; <span class="hljs-keyword">if</span> ((num & (num - <span class="hljs-params">1</span>)) !== <span class="hljs-params">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; <span class="hljs-keyword">return</span> (num & <span class="hljs-params">0x55555555</span>) === num; }; ``` ``` Python Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">isPowerOfFour</span><span class="hljs-params">(self, num: int)</span> -> bool:</span> <span class="hljs-keyword">if</span> num == <span class="hljs-params">1</span>: <span class="hljs-keyword">return</span> <span class="hljs-keyword">True</span> <span class="hljs-keyword">elif</span> num < <span class="hljs-params">4</span>: <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span> <span class="hljs-keyword">else</span>: <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> num & (num<span class="hljs-params">-1</span>) == <span class="hljs-params">0</span>: <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span> <span class="hljs-keyword">else</span>: <span class="hljs-keyword">return</span> num & <span class="hljs-params">0x55555555</span> == num <span class="hljs-title"># 另一種解法：將數字轉化為二進制表示的字符串，利用字符串的相關操作進行判斷</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">isPowerOfFour</span><span class="hljs-params">(self, num: int)</span> -> bool:</span> binary_num = bin(num)[<span class="hljs-params">2</span>:] <span class="hljs-keyword">return</span> binary_num.strip(<span class="hljs-string">'0'</span>) == <span class="hljs-string">'1'</span> <span class="hljs-keyword">and</span> len(binary_num) % <span class="hljs-params">2</span> == <span class="hljs-params">1</span> ``` ``` **復雜度分析** - 時間復雜度：O(1)O(1)O(1) - 空間復雜度：O(1)O(1)O(1) 更多題解可以訪問我的LeetCode題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經37K star啦。 關注公眾號力扣加加，努力用清晰直白的語言還原解題思路，并且有大量圖解，手把手教你識別套路，高效刷題。