題目描述
難度級別：簡單
給定一個整數(shù)，寫一個函數(shù)來判斷它是否是 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
進階：
你能不使用循環(huán)或者遞歸來完成本題嗎？
解題思路
迭代
與2的冪算法類似纯出，這里連續(xù)對數(shù)n模4蚯妇，若不為0，終止循環(huán)暂筝，判斷數(shù)n是否為1箩言，若為1則 返回true，否則false焕襟。
const isPowerOfFour = function(n) {
if (n < 1) return false
while(n % 4 === 0) n /= 4
return n === 1
};
時間復雜度：O(log n)
空間復雜度：O(1)
數(shù)學
一個數(shù)n是否是4的冪陨收，它滿足 n = 4^x，則有 x = log4(n) = 1/2log2(n)鸵赖，x為整數(shù)务漩，則log2(n)應該為偶數(shù)。
const isPowerOfFour = n => Math.log2(n) % 2 === 0
時間復雜度：O(1)
空間復雜度：O(1)
位運算
2的冪通過位運算計算是 n & (n - 1) === 0且n > 0
2的冪它褪，在二進制中表示
1： 0000 0001
2: 0000 0010
4: 0000 0100
8: 0000 1000
16: 0001 0000
32: 0010 0000
發(fā)現(xiàn)4的冪在偶數(shù)位上位1饵骨，其他位為0，則他與數(shù)字數(shù)字 (101010...10)2進制做與運算為0茫打，(101010...10)2進制換算成16進制為0xaaaaaaaa居触，則有
const isPowerOfFour = function(n) {
return n > 0 && (n & (n - 1)) === 0 && (n & 0xaaaaaaaa) === 0
};
時間復雜度：O(1)
空間復雜度：O(1)
位運算加數(shù)學
2^k為2得冪，位運算計算是 n & (n - 1) === 0且n > 0
2的偶數(shù)次方是4的冪包吝，奇數(shù)則不是
2^2k 則是4的冪饼煞，2^(2k+1)則不是
2^2k = 4^k = (3+1)^k , (3+1)^k % 3 === 1
2^(2k+1) = 2 * 4^k = 2 * (3+1)^k , 2 * (3+1)^k % 3 === 2
則有
const isPowerOfFour = n => (n & (n - 1)) === 0 && n % 3 === 1
時間復雜度：O(1)
空間復雜度：O(1)
題目來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/power-of-four
