4的幂
原创
题目描述
难度级别：简单
给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。
整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4x
示例 1：
输入：n = 16 输出：true
示例 2：
输入：n = 5 输出：false
示例 3：
输入：n = 1 输出：true
提示：
-231 <= n <= 231 - 1
进阶：
你能不使用循环或者递归来完成本题吗？
解题思路
迭代
与2的幂算法类似，这里连续对数n模4，若不为0，终止循环，判断数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)
数学
一个数n是否是4的幂，它满足 n = 4^x，则有 x = log4(n) = 1/2log2(n)，x为整数，则log2(n)应该为偶数。
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发现4的幂在偶数位上位1，其他位为0，则他与数字数字 (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)
位运算加数学
2^k为2得幂，位运算计算是 n & (n - 1) === 0且n > 0
2的偶数次方是4的幂，奇数则不是
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
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。