题目
给定一个整数，写一个函数来判断它是否是 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$
进阶：你能不使用循环或者递归来完成本题吗？
解答
- 循环
直接使用循环进行n/=4的操作,到最后n小于3时根据n是否为1来判断原本的n是否为4的幂次
class Solution {
public:
bool isPowerOfFour(int n) {
while(n > 3) {
if (n % 4 == 0) { // 判断n是否是4的整倍数 （在n大于3的情况下）
n /= 4;
}
else return false; // 如果不是直接返回false
}
if (n == 1) return true; // /=操作结束后判断n是否为1 or n本来就为1的时候应该直接返回true
return false;
}
};- 递归
如题，直接递归就完事了
class Solution {
public:
bool isPowerOfFour(int n) {
if (n == 1 || n == 4) return true; // 返回true的条件
else if (n > 4) {
if (n % 4 != 0) return false; // 余数不为0 直接返回false
else return isPowerOfFour(n / 4); // 通过递归完成对n的更新
}
return false;
}
};- 使用位与运算符和掩码
首先，我们需要检查n是否为正数，并且它的二进制表示中只有一个1。这是因为4的幂次方的二进制表示中只有一个1。因此，如果n不是正数或者它的二进制表示中有多个1，则它不是4的幂。
其次，我们需要使用位运算来检查n是否为4的幂。我们可以使用位与运算符（&）和一个掩码来完成此操作。掩码是一个32位整数，它的二进制表示中只有偶数位为1，奇数位为0。如果n是4的幂，则它的二进制表示中的1只能在偶数位上出现。因此，如果我们将n与掩码进行位与运算，结果应该等于n本身。
最终，如果n既是正数且只有一个1，又是4的幂，则函数返回true；否则，返回false。
详细的说，当你看到一个整数n时，你需要确定它是否是4的幂次方。一个正整数n是4的幂次方，当且仅当它满足以下两个条件：
- n是正整数，并且它的二进制表示中只有一个1，例如1、4、16等；
- n可以表示为$4^k$的形式，其中k是一个非负整数。
因此，我们需要找到一种方法来检查n是否满足这两个条件。在不使用循环或递归的前提下，我们可以使用位运算来实现这个目标。
首先，我们检查n是否为正整数，这可以通过检查n是否大于0来实现。然后，我们需要检查n的二进制表示中只有一个1。如果我们将n减去1，那么所有在原来的二进制表示中为1的位都会变成0，而它后面的所有位都会变成1。例如，如果n的二进制表示为10000，那么n-1的二进制表示为01111。如果我们将n和n-1进行位与运算，结果将为0。因为n的二进制表示中只有一个1，所以n-1的二进制表示中所有的1都位于n的二进制表示中的0的位置上，因此它们不会在位与运算中重叠。如果n的二进制表示中有多个1，则n-1的二进制表示中将有一个以上的1与n的二进制表示中的1重叠，这样位与运算的结果将不为0。
接下来，我们需要使用位运算来检查n是否可以表示为4的幂。我们知道，4的幂的二进制表示中的1只能出现在偶数位上，例如100、10000、1000000等。因此，我们可以使用一个掩码来将所有奇数位上的位设置为0，而偶数位上的位设置为1。这个掩码可以是0x55555555，它的二进制表示为01010101010101010101010101010101。如果我们将n与这个掩码进行位与运算，结果将为n本身，如果n不能表示为4的幂，则结果将不为n本身。
最后，如果n既是正整数且只有一个1，又是4的幂，则函数返回true，否则返回false。
class Solution {
public:
bool isPowerOfFour(int n) {
// 检查n是否为正数，且n的二进制表示只有一个1，且n是否为4的幂
return (n > 0) && ((n & (n - 1)) == 0) && ((n & 0x55555555) == n);
}
};