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