題目描述
給你一個(gè)整數(shù) n雀瓢，請(qǐng)你判斷該整數(shù)是否是 2 的冪次方枢析。如果是，返回 true 刃麸；否則醒叁，返回 false 。
如果存在一個(gè)整數(shù) x 使得 n == 2x 嫌蚤，則認(rèn)為 n 是 2 的冪次方辐益。
示例 1：
輸入：n = 1
輸出：true
解釋：20 = 1
示例 2：
輸入：n = 16
輸出：true
解釋：24 = 16
示例 3：
輸入：n = 3
輸出：false
示例 4：
輸入：n = 4
輸出：true
示例 5：
輸入：n = 5
輸出：false
提示：
-2^31 <= n <= 2^31 - 1
題解
思路1:輾除法
static public func isPowerOfTwo1(_ n:Int) -> Bool {
var n = n
while n>0 && n%2==0 {
n = n/2
}
return n==1
}
思路2:二進(jìn)制表示 n & (n - 1) == 0
一個(gè)數(shù)n 是2 的冪，當(dāng)且僅當(dāng)n是正整數(shù)脱吱，并且n的二進(jìn)制表示中僅包含1個(gè)1
位運(yùn)算技巧n&(n-1),該位運(yùn)算技巧可以直接將n二進(jìn)制表示的最低位1移除
假設(shè)n的二進(jìn)制表示為(a10?0)2智政，其中a表示若干個(gè)高位，1表示最低位的那個(gè)1箱蝠，0?0 表示后面的若干個(gè)0续捂，那么n?1 的二進(jìn)制表示為：(a01?1)2
我們將(a10?0)2與(a01?1)2 進(jìn)行按位與運(yùn)算垦垂，高位a不變，在這之后的所有位都會(huì)變?yōu)?牙瓢，這樣我們就將最低位的那個(gè)1移除了
n & (n - 1) == 0,則表示n為2的冪
static public func isPowerOfTwo2(_ n:Int) -> Bool {
return n>0 && (n&(n-1)==0)
}
思路3:二進(jìn)制表示 n & (-n) == n
一個(gè)數(shù)n 是2 的冪劫拗，當(dāng)且僅當(dāng)n是正整數(shù)，并且n的二進(jìn)制表示中僅包含1個(gè)1
位運(yùn)算技巧n&(-n),該位運(yùn)算技巧可以直接獲取n二進(jìn)制表示的最低位的1
由于負(fù)數(shù)是按照補(bǔ)碼規(guī)則在計(jì)算機(jī)中存儲(chǔ)的矾克，?n 的二進(jìn)制表示為n的二進(jìn)制表示的每一位取反再加上1页慷，因此它的原理如下:
假設(shè)n的二進(jìn)制表示為(a10?0)2，其中a表示若干個(gè)高位胁附，1表示最低位的那個(gè)1酒繁，0?0 表示后面的若干個(gè)0，那么?n 的二進(jìn)制表示為：
(b01?1)2 + (1)2 = (b10?0)2,
其中b表示將a每一位取反控妻。我們將(a10?0)2與(b10?0)2進(jìn)行按位與運(yùn)算州袒，高位全部變?yōu)?，最低位的1以及之后的所有0不變弓候，這樣我們就獲取了n二進(jìn)制表示的最低位的1郎哭。
n & (-n) == n,則表示n為2的冪
static public func isPowerOfTwo3(_ n:Int) -> Bool {
return n>0 && (n&(-n)==n)
}
思路4:判斷是否為最大2的冪的約數(shù)
在題目給定的32位有符號(hào)整數(shù)的范圍內(nèi)，最大的2 的冪為 2^30 = 1073741824菇存。我們只需要判斷n 是否是2^30的約數(shù)即可
static public func isPowerOfTwo4(_ n:Int) -> Bool {
let big = 1<<30
return n>0 && (big%n == 0)
}
參考：https://leetcode-cn.com/problems/power-of-two
https://leetcode-cn.com/problems/power-of-two/solution/2de-mi-by-leetcode-solution-rny3/
