4的幂_ 字节宝

题目描述

难度级别：简单

给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4x

输入：n = 16 输出：true

输入：n = 5 输出：false

输入：n = 1 输出：true

-231 <= n <= 231 - 1

你能不使用循环或者递归来完成本题吗？

与2的幂算法类似，这里连续对数n模4，若不为0，终止循环，判断数n是否为1，若为1则返回true，否则false。

代码语言：javascript复制

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)应该为偶数。

代码语言：javascript复制

const isPowerOfFour = n => Math.log2(n) % 2 === 0

时间复杂度：O(1) 空间复杂度：O(1)

2的幂通过位运算计算是 n & (n - 1) === 0且n > 0

2的幂，在二进制中表示

代码语言：javascript复制

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，则有

代码语言：javascript复制

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

则有

代码语言：javascript复制

const isPowerOfFour = n => (n & (n - 1)) === 0 && n % 3 === 1

时间复杂度：O(1) 空间复杂度：O(1)

题目来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/power-of-four

0 人点赞