【LeetCode】4 的幂还可以这样解 ？

原题信息

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

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

n的取值范围：-2^31 <= n <= 2^31-1

输入：n = 16
输出：true

输入：n = 5
输出：false

输入：n = 1
输出：true

看到这个题的第一想法是什么呢？

菜编思路

因为之前做过 2 的幂，所以想想能不能使用同样的套路，先找找两者之间的联系

1. 4 的幂一定是 2 的幂，但是 2 的幂不一定是 4 的幂
   
2. 假设 4^k=n，那么就有2^(2k)=n，转化一下就是2^k * 2^k = n
   
3. 于是开始想先对 n 进行开方，然后再判断这个数是不是 2 的幂
   
4. 问题转化成自己熟悉的解决方案，有一点需要注意，如果n的开方结果很有可能是浮点数，需要接收结果的类型。
   
5. 接着我们就判断，开方的结果是否有小数位，则不是 4 的幂，如果无小数位，则判断是否为 2 的幂，如果是，则也是 4 的幂
   
6. 实际运行时间在一定程度上跟编程语言的开方函数有关
   

这个方法实现起来可能有点复杂，不如我们想象是否还有其他优雅的操作？

解法二

假设我们还是简单粗暴一点，使用循环的操作，判断余数是否为 0

这个很容易理解，直接上代码

public boolean isPowerOfFour(int n) {
  if (n < 1)
    return false;
  while (n > 1) {
    if (n % 4 != 0)
      return false;
    n = n >> 2;
  }
  return true;
}

这段代码也不是不能用，能正常解决问题，但是这个循环不够优雅，当我们使用循环的时候，要尽量减少循环体中判断等操作的次数，提高程序的运行效率

修改后的代码如下所示：

public boolean isPowerOfFour(int n) {
  if (n < 1)
    return false;
  while (n % 4 == 0) {
    n = n >> 2;
  }
  return n == 1;
}

循环体中的循环由 2 次操作变成了 1 次操作，虽然看起来微不足道，但是在数据量很大的时候，还是有点差距的

解法三

1. 借助 2 次幂相同的操作思路，转化二进制的操作
   
2. 4 的幂转化二进制，有一个特点，那就是只有一个 1 在奇数位上
   
3. 如果转化 2 进制，在偶数位上存在 1 ，那么这个数一定不是 4 的幂
   
4. 因为知道 n 的取值范围，所以我们可以确定一个偶数位全是 1 的数进行位与运算
   

代码参考

// 来自leetcode官方解法
public boolean isPowerOfFour(int n) {
  return n > 0 && (n & (n - 1)) == 0 && (n & 0xaaaaaaaa) == 0;
}

解法四

在leetcode官方解法中，还看到一个很有意思的方法，就是借助取模操作，4 的幂除以 3 的余数一定是 1，这样就可以通过 n 除以 3 的余数是不是 1 来判断是否是 4 的幂。这个真的妙啊～

public boolean isPowerOfFour(int n) {
    return n > 0 && (n & (n - 1)) == 0 && n % 3 == 1;
}

解法三、解法四的时间复杂度和空间复杂度都是O(1)

除此以外还有很多解法，比如转化四进制，进行位与运算，这就和二进制运算判断 2 的幂完全一样了。在确定范围 n 的取值范围情况下，我们还可以使用哈希表的方式，时间复杂度和空间复杂度也都是O(1)