題目
給你一個(gè)整數(shù) 蔫巩，請你判斷該整數(shù)是否是
的冪次方。如果是快压，返回
true圆仔；否則，返回 false蔫劣。
如果存在一個(gè)整數(shù) 使得
坪郭，則認(rèn)為
是
的冪次方。
示例 1：
- 輸入：
n = 1- 輸出：
true- 解釋：
= 1
示例 2：
- 輸入：
n = 16- 輸出：
true- 解釋：
= 16
示例 3：
- 輸入：
n = 3- 輸出：
false
示例 4：
- 輸入：
n = 4- 輸出：
true
方法一：二進(jìn)制表示
思路及解法
一個(gè)數(shù) 是 2 的冪脉幢，當(dāng)且僅當(dāng)
是正整數(shù)歪沃，并且
的二進(jìn)制表示中僅包含 1 個(gè) 1。
因此我們可以考慮使用位運(yùn)算嫌松，將 的二進(jìn)制表示中最低位的那個(gè) 1 提取出來沪曙，再判斷剩余的數(shù)值是否為 0 即可。下面介紹兩種常見的與「二進(jìn)制表示中最低位」相關(guān)的位運(yùn)算技巧萎羔。
第一個(gè)技巧是
其中 表示按位與運(yùn)算液走。該位運(yùn)算技巧可以直接將
二進(jìn)制表示的最低位
移除，它的原理如下：
假設(shè)
的二進(jìn)制表示為
，其中
表示若干個(gè)高位缘眶，
表示最低位的那個(gè) 1嘱根，
表示后面的若干個(gè)
，那么
的二進(jìn)制表示為：
我們將
進(jìn)行按位與運(yùn)算巷懈，高位
因此柔逼，如果 是正整數(shù)并且
蒋譬，那么
就是
的冪割岛。
第二個(gè)技巧是
其中 是
的相反數(shù)，是一個(gè)負(fù)數(shù)犯助。該位運(yùn)算技巧可以直接獲取
二進(jìn)制表示的最低位的
癣漆。
由于負(fù)數(shù)是按照補(bǔ)碼規(guī)則在計(jì)算機(jī)中存儲(chǔ)的， 的二進(jìn)制表示為
的二進(jìn)制表示的每一位取反再加上
剂买，因此它的原理如下：
假設(shè)
表示后面的若干個(gè)
的二進(jìn)制表示為：
其中
表示將
進(jìn)行按位與運(yùn)算坐慰，高位全部變?yōu)?
因此赞咙，如果 是正整數(shù)并且
，那么
就是
的冪糟港。
代碼
class Solution {
func isPowerOfTwo(_ n: Int) -> Bool {
return n > 0 && (n & (n - 1)) == 0
}
}
class Solution {
func isPowerOfTwo(_ n: Int) -> Bool {
return n > 0 && (n & -n) == n
}
}
復(fù)雜度分析
時(shí)間復(fù)雜度：
攀操。
空間復(fù)雜度：
方法二：判斷是否為最大 2 的冪的約數(shù)
思路及解法
除了使用二進(jìn)制表示判斷之外秸抚，還有一種較為取巧的做法速和。
在題目給定的 位有符號整數(shù)的范圍內(nèi)，最大的
的冪為
剥汤。我們只需要判斷
是否是
的約數(shù)即可健芭。
代碼
class Solution {
func isPowerOfTwo(_ n: Int) -> Bool {
let BIG = 1 << 30
return n > 0 && BIG % n == 0
}
}
復(fù)雜度分析
時(shí)間復(fù)雜度：
空間復(fù)雜度：
