資訊專(zhuān)欄INFORMATION COLUMN
題目來(lái)源于 LeetCode 上第 342 號(hào)問(wèn)題：4 的冪。題目難度為 Easy，目前通過(guò)率為 45.3% 。
題目描述給定一個(gè)整數(shù) (32 位有符號(hào)整數(shù))，請(qǐng)編寫(xiě)一個(gè)函數(shù)來(lái)判斷它是否是 4 的冪次方。
示例 1:
輸入: 16 輸出: true
示例 2:
輸入: 5 輸出: false
進(jìn)階：
你能不使用循環(huán)或者遞歸來(lái)完成本題嗎？
這道題最直接的方法就是不停的去除以 4 ，看最終結(jié)果是否為 1 ，參見(jiàn)代碼如下：
class Solution {
public boolean isPowerOfFour(int num) {
while ( (num != 0) && (num % 4 == 0)) {
num /= 4;
}
return num == 1;
}
}
不過(guò)這段代碼使用了 循環(huán) ，逼格不夠高。
對(duì)于一個(gè)整數(shù)而言，如果這個(gè)數(shù)是 4 的冪次方，那它必定也是 2 的冪次方。
我們先將 2 的冪次方列出來(lái)找一下其中哪些數(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ù)位。
之前在小吳的文章中判斷一個(gè)是是否是 2 的冪次方數(shù)使用的是位運(yùn)算 n & ( n - 1 )。同樣的，這里依舊可以使用位運(yùn)算：將這個(gè)數(shù)與特殊的數(shù)做位運(yùn)算。
這個(gè)特殊的數(shù)有如下特點(diǎn)：
足夠大，但不能超過(guò) 32 位，即最大為 1111111111111111111111111111111（ 31 個(gè) 1）
它的二進(jìn)制表示中奇數(shù)位為 1 ，偶數(shù)位為 0
符合這兩個(gè)條件的二進(jìn)制數(shù)是：
1010101010101010101010101010101
如果用一個(gè) 4 的冪次方數(shù)和它做與運(yùn)算，得到的還是 4 的冪次方數(shù)。
將這個(gè)二進(jìn)制數(shù)轉(zhuǎn)換成 16 進(jìn)制表示：0x55555555 。有沒(méi)有感覺(jué)逼格更高點(diǎn)。。。
圖片描述 代碼實(shí)現(xiàn)class Solution {
public boolean isPowerOfFour(int num) {
if (num <= 0)
return false;
//先判斷是否是 2 的冪
if ((num & num - 1) != 0)
return false;
//如果與運(yùn)算之后是本身則是 4 的冪
if ((num & 0x55555555) == num)
return true;
return false;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/76260.html
摘要：題目難度為，目前通過(guò)率為。這個(gè)特殊的數(shù)有如下特點(diǎn)足夠大，但不能超過(guò)位，即最大為個(gè)它的二進(jìn)制表示中奇數(shù)位為，偶數(shù)位為符合這兩個(gè)條件的二進(jìn)制數(shù)是如果用一個(gè)的冪次方數(shù)和它做與運(yùn)算，得到的還是的冪次方數(shù)。將這個(gè)二進(jìn)制數(shù)轉(zhuǎn)換成進(jìn)制表示。 題目來(lái)源于 LeetCode 上第 342 號(hào)問(wèn)題：4 的冪。題目難度為 Easy，目前通過(guò)率為 45.3% 。 題目描述 給定一個(gè)整數(shù) (32 位有符號(hào)整數(shù))...
摘要：位算法的效率有多快我就不說(shuō)，不信你可以去用億個(gè)數(shù)據(jù)模擬一下，今天給大家講一講位運(yùn)算的一些經(jīng)典例子。不過(guò)，最重要的不是看懂了這些例子就好，而是要在以后多去運(yùn)用位運(yùn)算這些技巧，當(dāng)然，采用位運(yùn)算，也是可以裝逼的，不信，你往下看。位算法的效率有多快我就不說(shuō)，不信你可以去用 10 億個(gè)數(shù)據(jù)模擬一下，今天給大家講一講位運(yùn)算的一些經(jīng)典例子。不過(guò)，最重要的不是看懂了這些例子就好，而是要在以后多去運(yùn)用位運(yùn)算這...
摘要：原題給定一個(gè)整數(shù)，編寫(xiě)一個(gè)函數(shù)來(lái)判斷它是否是的冪次方。按位與的取值規(guī)則如下，等于等于等于等于。我們可以利用這個(gè)特性，判斷數(shù)字是否為的次冪。 showImg(https://segmentfault.com/img/remote/1460000020181837?w=1321&h=729); 原題 給定一個(gè)整數(shù)，編寫(xiě)一個(gè)函數(shù)來(lái)判斷它是否是 2 的冪次方。 示例 1: 輸入: 1 輸出:...
摘要：整除法復(fù)雜度時(shí)間空間思路最簡(jiǎn)單的解法，不斷將原數(shù)除以，一旦無(wú)法整除，余數(shù)不為，則說(shuō)明不是的冪，如果整除到，說(shuō)明是的冪。二進(jìn)制位計(jì)數(shù)法復(fù)雜度時(shí)間空間思路的冪有一個(gè)特性，就是它的二進(jìn)制表達(dá)中只有開(kāi)頭是，后面全是。 Power of Two Given an integer, write a function to determine if it is a power of two. 整除法...
閱讀 2580·2021-11-23 09:51
閱讀 2495·2021-09-30 09:48
閱讀 1094·2021-09-10 10:51
閱讀 2229·2021-08-12 13:22
閱讀 3583·2021-08-11 10:24
閱讀 2183·2019-08-30 15:55
閱讀 653·2019-08-30 14:05
閱讀 3220·2019-08-30 13:03
