資訊專欄INFORMATION COLUMN
摘要：題目難度為，目前通過率為。這個特殊的數有如下特點足夠大，但不能超過位，即最大為個它的二進制表示中奇數位為，偶數位為符合這兩個條件的二進制數是如果用一個的冪次方數和它做與運算，得到的還是的冪次方數。將這個二進制數轉換成進制表示。
題目來源于 LeetCode 上第 342 號問題：4 的冪。題目難度為 Easy，目前通過率為 45.3% 。
題目描述給定一個整數 (32 位有符號整數)，請編寫一個函數來判斷它是否是 4 的冪次方。
示例 1:
輸入: 16 輸出: true
示例 2:
輸入: 5 輸出: false
進階：
你能不使用循環或者遞歸來完成本題嗎？
這道題最直接的方法就是不停的去除以 4 ，看最終結果是否為 1 ，參見代碼如下：
class Solution {
public boolean isPowerOfFour(int num) {
while ( (num != 0) && (num % 4 == 0)) {
num /= 4;
}
return num == 1;
}
}
不過這段代碼使用了 循環 ，逼格不夠高。
對于一個整數而言，如果這個數是 4 的冪次方，那它必定也是 2 的冪次方。
我們先將 2 的冪次方列出來找一下其中哪些數是 4 的冪次方。
| 十進制 | 二進制 |
|---|---|
| 2 | 10 |
| 4 | 100 （1 在第 3 位） |
| 8 | 1000 |
| 16 | 10000（1 在第 5 位） |
| 32 | 100000 |
| 64 | 1000000（1 在第 7 位） |
| 128 | 10000000 |
| 256 | 100000000（1 在第 9 位） |
| 512 | 1000000000 |
| 1024 | 10000000000（1 在第 11 位） |
找一下規律： 4 的冪次方的數的二進制表示 1 的位置都是在奇數位。
之前在小吳的文章中判斷一個是是否是 2 的冪次方數使用的是位運算 n & ( n - 1 )。同樣的，這里依舊可以使用位運算：將這個數與特殊的數做位運算。
這個特殊的數有如下特點：
足夠大，但不能超過 32 位，即最大為 1111111111111111111111111111111（ 31 個 1）
它的二進制表示中奇數位為 1 ，偶數位為 0
符合這兩個條件的二進制數是：
1010101010101010101010101010101
如果用一個 4 的冪次方數和它做與運算，得到的還是 4 的冪次方數。
將這個二進制數轉換成 16 進制表示：0x55555555 。有沒有感覺逼格更高點。。。
圖片描述 代碼實現class Solution {
public boolean isPowerOfFour(int num) {
if (num <= 0)
return false;
//先判斷是否是 2 的冪
if ((num & num - 1) != 0)
return false;
//如果與運算之后是本身則是 4 的冪
if ((num & 0x55555555) == num)
return true;
return false;
}
}
?? 看完三件事：
如果你覺得這篇內容對你挺有啟發，我想邀請你幫我三個忙：
點贊，讓更多的人也能看到這篇內容（收藏不點贊，都是耍流氓 -_-）
關注我和專欄，讓我們成為長期關系
關注公眾號「五分鐘學算法」，第一時間閱讀最新的算法文章，公眾號后臺回復 1024 送你 50 本 算法編程書籍。
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/76248.html
摘要：位算法的效率有多快我就不說，不信你可以去用億個數據模擬一下，今天給大家講一講位運算的一些經典例子。不過，最重要的不是看懂了這些例子就好，而是要在以后多去運用位運算這些技巧，當然，采用位運算，也是可以裝逼的，不信，你往下看。位算法的效率有多快我就不說，不信你可以去用 10 億個數據模擬一下，今天給大家講一講位運算的一些經典例子。不過，最重要的不是看懂了這些例子就好，而是要在以后多去運用位運算這...
摘要：解決方案異或操作異或運算是對于二進制數字而言的，比如說一個有兩個二進制，如果兩個值不相同，則異或結果為。比如說，本質上其實是和的每一對比特位執行異或操作，等價于下面數字對應的二進制數字對應的二進制數字對應的二進制因此的結果就為啦。 新年第一篇文章，先祝大家新年快樂！！那么接下來進入正文。 前言 前陣子突發奇想，突然開始刷leetcode。其中刷到了一道有意思的題目，發現這道題是當時秋招...
摘要：重溫一個面試題內容數組內容為數組內容為個英文字母，使用兩個線程分別輸入兩個數組，打印內容為這樣的規律提取一下核心內容，去除次要內容兩個線程需要交替執行，打印數字的線程需要先執行，數組打印完畢后線程需要結束。 一道多線程面試題引起的自我救贖 近日去一個知名互聯網企業參加面試，之前準備多多信心滿滿，但是面試一開始就是一道不起眼的編程題 數組A內容為 1,2,3,4...52 ,數組B內容...
摘要：對于這種會退出的情況，數組顯然不能像鏈表一樣直接斷開，因此采用標記法先生成一個長度為的布爾型數組，用填充。中對整個進行遍歷才能得到此時數組中的數量。 文中的速度測試部分，時間是通過簡單的 System.currentTimeMillis() 計算得到的， 又由于 Java 的特性，每次測試的結果都不一定相同， 對于低數量級的情況有 ± 20 的浮動，對于高數量級的情況有的能有 ± 10...
閱讀 2814·2021-11-18 10:02
閱讀 3673·2021-11-15 17:59
閱讀 2306·2021-09-06 15:00
閱讀 3344·2019-08-29 16:58
閱讀 1056·2019-08-26 10:34
閱讀 1581·2019-08-26 10:15
閱讀 1286·2019-08-26 10:11
閱讀 2713·2019-08-23 18:33
