342. 4 的幂

🟢   🔖  位运算 递归 数学  🔗 力扣 LeetCode

题目

Given an integer n, return true if it is a power of four. Otherwise, return false.

An integer n is a power of four, if there exists an integer x such that n == 4^x.

Example 1:

Input: n = 16

Output: true

Example 2:

Input: n = 5

Output: false

Example 3:

Input: n = 1

Output: true

Constraints:

• -2^31 <= n <= 2^31 - 1

Follow up: Could you solve it without loops/recursion?

题目大意

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

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

示例 1：

输入： n = 16

输出： true

示例 2：

输入： n = 5

输出： false

示例 3：

输入： n = 1

输出： true

提示：

• -2^31 <= n <= 2^31 - 1

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

解题思路

抱歉，我理解错了问题。下面是关于判断一个数是否是 4 的幂次方的正确解题思路。

解题思路

思路一：累除法

1. 如果 n 小于等于 0，直接返回 false，因为负数或零不可能是 4 的幂次方。
2. 对于一个正整数，如果它是 4 的幂次方，那么它应该可以不断被 4 整除，直到结果为 1。
3. 如果 n 不等于 1，并且能被 4 整除，就不断除以 4。
   • 最终若得到 1，说明 n 是 4 的幂次方。
   • 否则不是。

复杂度分析

• 时间复杂度：O(log_4(n))，每次除以 4，直到结果为 1，最多需要对数次操作。
• 空间复杂度：O(1)，只使用常数空间。

---

思路二：位运算法

4 的幂次方具有一个特殊的性质：它的二进制表示形式只包含一个 1，并且这个 1 只能出现在偶数位上。例如，4 的幂次方的二进制形式如下：

• 4^0 = 1 -> 0001
• 4^1 = 4 -> 0100
• 4^2 = 16 -> 10000
• 4^3 = 64 -> 1000000

利用这一性质，可以通过位运算来判断一个数是否为 4 的幂次方：

• n > 0：n 必须是正数。
• n & (n - 1) === 0：n 必须是 2 的幂次方。
• n % 3 === 1：这意味着 n 必须是 4 的幂次方，这是判断 n 是否是 4 的幂次方的关键条件。

复杂度分析

• 时间复杂度：O(1)，因为位运算是常数时间操作。
• 空间复杂度：O(1)，只使用常数空间。

---

思路三：数学公式法

• 可以利用对数的性质，若 n 是 4 的幂次方，则对 n 取对数（底数为 4）后应该是整数。
• 公式：log_4(n) = log(n) / log(4)
• 如果 log_4(n) 是整数，则 n 是 4 的幂次方。

复杂度分析

• 时间复杂度：O(1)，只需要计算对数和指数操作。
• 空间复杂度：O(1)，只使用常数空间。

代码实现

累除法

/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfFour = function (n) {
	if (n <= 0) return false;
	while (n % 4 === 0) {
		n /= 4;
	}
	return n === 1;
};

位运算法

/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfFour = function (n) {
	return n > 0 && (n & (n - 1)) === 0 && n % 3 === 1;
};

数学公式法

/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfFour = function (n) {
	return n > 0 && Number.isInteger(Math.log(n) / Math.log(4));
};

相关题目

题号	标题	题解	标签	难度	力扣
231	2 的幂	[✓]	位运算 递归 数学	🟢	🀄️ 🔗
326	3 的幂	[✓]	递归 数学	🟢	🀄️ 🔗