0342-4的幂

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 15:32:47 2023-09-13 15:32:47 Updated    

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

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

示例 1：

**输入：** n = 16
**输出：** true

示例 2：

**输入：** n = 5
**输出：** false

示例 3：

**输入：** n = 1
**输出：** true

提示：

  • -231 <= n <= 231 - 1

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

前言

如果 $n$ 是 $4$ 的幂，那么 $n$ 一定也是 $2$ 的幂。因此我们可以首先判断 $n$ 是否是 $2$ 的幂，在此基础上再判断 $n$ 是否是 $4$ 的幂。

判断 $n$ 是否是 $2$ 的幂可以参考「231. 2的幂的官方题解 」。由于这一步的方法有很多种，在下面的题解中，我们使用

$$
\texttt{n & (n - 1)}
$$

这一方法进行判断。

方法一：二进制表示中 $1$ 的位置

思路与算法

如果 $n$ 是 $4$ 的幂，那么 $n$ 的二进制表示中有且仅有一个 $1$，并且这个 $1$ 出现在从低位开始的第偶数个二进制位上（这是因为这个 $1$ 后面必须有偶数个 $0$）。这里我们规定最低位为第 $0$ 位，例如 $n=16$ 时，$n$ 的二进制表示为

$$
(10000)_2
$$

唯一的 $1$ 出现在第 $4$ 个二进制位上，因此 $n$ 是 $4$ 的幂。

由于题目保证了 $n$ 是一个 $32$ 位的有符号整数，因此我们可以构造一个整数 mask，它的所有偶数二进制位都是 $0$，所有奇数二进制位都是 $1$。这样一来，我们将 $n$ 和 mask 进行按位与运算，如果结果为 $0$，说明 $n$ 二进制表示中的 $1$ 出现在偶数的位置，否则说明其出现在奇数的位置。

根据上面的思路，mask 的二进制表示为：

$$
\textit{mask} = (10101010101010101010101010101010)_2
$$

我们也可以将其表示成 $16$ 进制的形式，使其更加美观：

$$
\textit{mask} = (\text{AAAAAAAA})_{16}
$$

代码

[sol1-C++]
1
2
3
4
5
6
class Solution {
public:
    bool isPowerOfFour(int n) {
        return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0;
    }
};
[sol1-Java]
1
2
3
4
5
class Solution {
    public boolean isPowerOfFour(int n) {
        return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0;
    }
}
[sol1-C#]
1
2
3
4
5
public class Solution {
    public bool IsPowerOfFour(int n) {
        return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0;
    }
}
[sol1-Python3]
1
2
3
class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        return n > 0 and (n & (n - 1)) == 0 and (n & 0xaaaaaaaa) == 0
[sol1-JavaScript]
1
2
3
var isPowerOfFour = function(n) {
    return n > 0 && (n & (n - 1)) === 0 && (n & 0xaaaaaaaa) === 0;
};
[sol1-Golang]
1
2
3
func isPowerOfFour(n int) bool {
    return n > 0 && n&(n-1) == 0 && n&0xaaaaaaaa == 0
}
[sol1-C]
1
2
3
bool isPowerOfFour(int n) {
    return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0;
}

复杂度分析

  • 时间复杂度：$O(1)$。

  • 空间复杂度：$O(1)$。

思考

事实上，我们令：

$$
\textit{mask} = (\text{2AAAAAAA})_{16}
$$

也可以使得上面的判断满足要求，读者可以思考其中的原因。

提示：$n$ 是一个「有符号」的 $32$ 位整数。

方法二：取模性质

思路与算法

如果 $n$ 是 $4$ 的幂，那么它可以表示成 $4^x$ 的形式，我们可以发现它除以 $3$ 的余数一定为 $1$，即：

$$
4^x \equiv (3+1)^x \equiv 1^x \equiv 1 \quad (\bmod ~3)
$$

如果 $n$ 是 $2$ 的幂却不是 $4$ 的幂，那么它可以表示成 $4^x \times 2$ 的形式，此时它除以 $3$ 的余数一定为 $2$。

因此我们可以通过 $n$ 除以 $3$ 的余数是否为 $1$ 来判断 $n$ 是否是 $4$ 的幂。

代码

[sol2-C++]
1
2
3
4
5
6
class Solution {
public:
    bool isPowerOfFour(int n) {
        return n > 0 && (n & (n - 1)) == 0 && n % 3 == 1;
    }
};
[sol2-Java]
1
2
3
4
5
class Solution {
    public boolean isPowerOfFour(int n) {
        return n > 0 && (n & (n - 1)) == 0 && n % 3 == 1;
    }
}
[sol2-C#]
1
2
3
4
5
public class Solution {
    public bool IsPowerOfFour(int n) {
        return n > 0 && (n & (n - 1)) == 0 && n % 3 == 1;
    }
}
[sol2-Python3]
1
2
3
class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        return n > 0 and (n & (n - 1)) == 0 and n % 3 == 1
[sol2-JavaScript]
1
2
3
var isPowerOfFour = function(n) {
    return n > 0 && (n & (n - 1)) === 0 && n % 3 === 1;
};
[sol2-Golang]
1
2
3
func isPowerOfFour(n int) bool {
    return n > 0 && n&(n-1) == 0 && n%3 == 1
}
[sol2-C]
1
2
3
bool isPowerOfFour(int n) {
    return n > 0 && (n & (n - 1)) == 0 && n % 3 == 1;
}

复杂度分析

  • 时间复杂度：$O(1)$。

  • 空间复杂度：$O(1)$。

✨扣友帮帮团 - 互动答疑

讨论.jpg{:width=260px}

即日起 - 5 月 30 日，点击 这里  前往「扣友帮帮团 」活动页，把你遇到的问题大胆地提出来，让扣友为你解答～

🎁 奖励规则

被采纳数量排名 1～3 名：「力扣极客套装」 *1 并将获得「力扣神秘应援团」内测资格
被采纳数量排名 4～10 名：「力扣鼠标垫」 *1 并将获得「力扣神秘应援团」内测资格
「诲人不倦」：活动期间「解惑者」只要有 1 个回答被采纳，即可获得 20 LeetCoins 奖励！
「求知若渴」：活动期间「求知者」在活动页发起一次符合要求的疑问帖并至少采纳一次「解惑者」的回答，即可获得 20 LeetCoins 奖励！

活动详情猛戳链接了解更多：🐞 你有 BUG 我来帮 - 力扣互动答疑季

 Comments
On this page
0342-4的幂
  1. ✨扣友帮帮团 - 互动答疑
    1. 🎁 奖励规则