难度: Easy
给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。
整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4x
示例 1：
输入：n = 16 输出：true
示例 2：
输入：n = 5 输出：false
示例 3：
输入：n = 1 输出：true
提示：
-231 <= n <= 231 - 1
进阶：你能不使用循环或者递归来完成本题吗？
Submission
运行时间: 18 ms
内存: 15.9 MB
class Solution:
def isPowerOfFour(self, n: int) -> bool:
return n > 0 and (n & (n - 1)) == 0 and (n & 0x55555555) != 0
Explain
该题解的思路是通过位运算来判断一个数是否为4的幂次方。首先检查该数是否大于0，然后利用 n&(n-1) 的位运算技巧判断其是否为2的幂次方。因为4的幂次方一定也是2的幂次方，但2的幂次方不一定是4的幂次方。4的幂次方的二进制表示中，只会在奇数位上有1，如 1，100，10000。所以再用 n&0x55555555 进行与运算，0x55555555 的二进制表示为 01010101010101010101010101010101，如果结果不为0，说明 n 是4的幂次方。
时间复杂度: O(1)
空间复杂度: O(1)
class Solution:
def isPowerOfFour(self, n: int) -> bool:
# 首先检查 n 是否大于0
# 然后判断 n 是否为2的幂次方，利用 n&(n-1) 的技巧
# 再判断 n 的二进制表示是否只在奇数位上有1，利用 n&0x55555555
return n > 0 and (n & (n - 1)) == 0 and (n & 0x55555555) != 0
Explore
在数学中，幂次方通常定义为正整数次幂的结果，且0的任何正数次幂都是0，而0的0次幂在某些定义中为1。对于4的幂次方来说，我们只考虑正整数的情况。负数或零不满足任何正整数的幂次方定义。因此，我们首先需要排除这些情况，确保n是一个正数，才有可能是4的幂次方。
对于任何整数n，如果n是2的幂次方，它的二进制表示中有且仅有一个位是1，其余都是0。例如，2（10）和8（1000），只有一个位为1。当执行n&(n-1)操作时，这个操作会将n的二进制表示中的最低位的1变成0。例如，8（1000）&7（0111）=0。如果n是2的幂次方，那么n&(n-1)将结果为0，因为只有一个1，并且这个1被移除后剩下的都是0。如果n不是2的幂次方，则其二进制中存在多于一个的1，因此n&(n-1)的结果不为0。
4的幂次方意味着该数可以表示为4^k，其中k是非负整数。因为4等于2的平方，所以4^k等于(2^2)^k=2^(2k)。这表明4的每个幂次方实际上是2的幂次方的一个特例，其中指数是偶数。在二进制表示中，2的幂次方（2^0, 2^1, 2^2, ...）分别表示为1（0001）、10（0010）、100（0100）等。可以看出，指数为偶数的情况下（如2^2, 2^4, 2^6），1总是出现在偶数位置（从右向左数，起始为1）。因为计算机科学中通常从零开始计数，这些偶数位置实际上是二进制表示中的奇数位（例如，第0位、第2位等）。