英文原文
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 == 4x.
Example 1:
Input: n = 16 Output: true
Example 2:
Input: n = 5 Output: false
Example 3:
Input: n = 1 Output: true
Constraints:
-231 <= n <= 231 - 1
Follow up: Could you solve it without loops/recursion?
中文题目
给定一个整数，写一个函数来判断它是否是 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$ 位的有符号整数，因此我们可以构造一个整数 $\textit{mask}$，它的所有偶数二进制位都是 $0$，所有奇数二进制位都是 $1$。这样一来，我们将 $n$ 和 $\textit{mask}$ 进行按位与运算，如果结果为 $0$，说明 $n$ 二进制表示中的 $1$ 出现在偶数的位置，否则说明其出现在奇数的位置。
根据上面的思路，$\textit{mask}$ 的二进制表示为：
$$
\textit{mask} = (10101010101010101010101010101010)_2
$$
我们也可以将其表示成 $16$ 进制的形式，使其更加美观：
$$
\textit{mask} = (\text{AAAAAAAA})_{16}
$$
代码
[sol1-C++]class Solution { public: bool isPowerOfFour(int n) { return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0; } };
[sol1-Java]class Solution { public boolean isPowerOfFour(int n) { return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0; } }
[sol1-C#]public class Solution { public bool IsPowerOfFour(int n) { return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0; } }
[sol1-Python3]class Solution: def isPowerOfFour(self, n: int) -> bool: return n > 0 and (n & (n - 1)) == 0 and (n & 0xaaaaaaaa) == 0
[sol1-JavaScript]var isPowerOfFour = function(n) { return n > 0 && (n & (n - 1)) === 0 && (n & 0xaaaaaaaa) === 0; };
[sol1-Golang]func isPowerOfFour(n int) bool { return n > 0 && n&(n-1) == 0 && n&0xaaaaaaaa == 0 }
[sol1-C]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++]class Solution { public: bool isPowerOfFour(int n) { return n > 0 && (n & (n - 1)) == 0 && n % 3 == 1; } };
[sol2-Java]class Solution { public boolean isPowerOfFour(int n) { return n > 0 && (n & (n - 1)) == 0 && n % 3 == 1; } }
[sol2-C#]public class Solution { public bool IsPowerOfFour(int n) { return n > 0 && (n & (n - 1)) == 0 && n % 3 == 1; } }
[sol2-Python3]class Solution: def isPowerOfFour(self, n: int) -> bool: return n > 0 and (n & (n - 1)) == 0 and n % 3 == 1
[sol2-JavaScript]var isPowerOfFour = function(n) { return n > 0 && (n & (n - 1)) === 0 && n % 3 === 1; };
[sol2-Golang]func isPowerOfFour(n int) bool { return n > 0 && n&(n-1) == 0 && n%3 == 1 }
[sol2-C]bool isPowerOfFour(int n) { return n > 0 && (n & (n - 1)) == 0 && n % 3 == 1; }
复杂度分析
时间复杂度：$O(1)$。
空间复杂度：$O(1)$。
✨扣友帮帮团 - 互动答疑
{:width=260px}即日起 - 5 月 30 日，点击 这里 前往「扣友帮帮团」活动页，把你遇到的问题大胆地提出来，让扣友为你解答～
🎁 奖励规则
被采纳数量排名 1～3 名：「力扣极客套装」 *1 并将获得「力扣神秘应援团」内测资格
被采纳数量排名 4～10 名：「力扣鼠标垫」 *1 并将获得「力扣神秘应援团」内测资格
「诲人不倦」：活动期间「解惑者」只要有 1 个回答被采纳，即可获得 20 LeetCoins 奖励！
「求知若渴」：活动期间「求知者」在活动页发起一次符合要求的疑问帖并至少采纳一次「解惑者」的回答，即可获得 20 LeetCoins 奖励！
活动详情猛戳链接了解更多：🐞 你有 BUG 我来帮 - 力扣互动答疑季
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 90852 | 175628 | 51.7% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
相似题目
| 题目 | 难度 |
|---|---|
| 2 的幂 | 简单 |
| 3的幂 | 简单 |
