題目
給定一個(gè)整數(shù)，寫(xiě)一個(gè)函數(shù)來(lái)判斷它是否是 4 的冪次方果港。如果是，返回 true糊昙；否則京腥，返回 false。
整數(shù) n 是 4 的冪次方需滿足：存在整數(shù) x 使得 n == 4x溅蛉。
示例 1：
- 輸入：
n = 16- 輸出：
true
示例 2：
- 輸入：
n = 5- 輸出：
false
示例 3：
- 輸入：
n = 1- 輸出：
true
提示：
-231 <= n <= 231 - 1
前言
如果 是
的冪公浪，那么
一定也是
的冪。因此我們可以首先判斷
是否是
的冪船侧，在此基礎(chǔ)上再判斷
是否是
的冪欠气。
判斷 是否是
的冪可以參考 2的冪的題解。由于這一步的方法有很多種镜撩，在下面的題解中预柒，我們使用
這一方法進(jìn)行判斷。
方法一：二進(jìn)制表示中 1 的位置
思路及解法
如果 是
的冪袁梗，那么
的二進(jìn)制表示中有且僅有一個(gè)
宜鸯，并且這個(gè)
出現(xiàn)在從低位開(kāi)始的第偶數(shù)個(gè)二進(jìn)制位上（這是因?yàn)檫@個(gè)
后面必須有偶數(shù)個(gè)
）。這里我們規(guī)定最低位為第
位遮怜，例如
時(shí)淋袖，
的二進(jìn)制表示為
唯一的 出現(xiàn)在第
個(gè)二進(jìn)制位上，因此
是
的冪锯梁。
由于題目保證了 是一個(gè)
位的有符號(hào)整數(shù)即碗，因此我們可以構(gòu)造一個(gè)整數(shù)
，它的所有偶數(shù)二進(jìn)制位都是
陌凳，所有奇數(shù)二進(jìn)制位都是
剥懒。這樣一來(lái)，我們將
和
進(jìn)行按位與運(yùn)算合敦，如果結(jié)果為
初橘，說(shuō)明
二進(jìn)制表示中的
出現(xiàn)在偶數(shù)的位置，否則說(shuō)明其出現(xiàn)在奇數(shù)的位置充岛。
根據(jù)上面的思路保檐， 的二進(jìn)制表示為：
我們也可以將其表示成 進(jìn)制的形式，使其更加美觀：
代碼
class Solution {
func isPowerOfFour(_ n: Int) -> Bool {
return n > 0 && n & (n - 1) == 0 && n % 3 == 1
}
}
復(fù)雜度分析
時(shí)間復(fù)雜度：
裸准。
空間復(fù)雜度：
方法二：取模性質(zhì)
思路及解法
如果 是
的冪，那么它可以表示成
的形式炒俱，我們可以發(fā)現(xiàn)它除以
的余數(shù)一定為
盐肃，即：
如果 是
的冪卻不是
的冪，那么它可以表示成
的形式权悟，此時(shí)它除以
的余數(shù)一定為
砸王。
因此我們可以通過(guò) 除以
的余數(shù)是否為
來(lái)判斷
是否是
的冪。
代碼
class Solution {
func isPowerOfFour(_ n: Int) -> Bool {
return n > 0 && n & (n - 1) == 0 && n & 0xaaaaaaaa == 0
}
}
復(fù)雜度分析
時(shí)間復(fù)雜度：
空間復(fù)雜度：
