342. Power of Four

题目

题意分析

题目要判定一个32位有符号整数是否是4的幂，只有正数才可能是4的幂。

本题考点

判定4的幂。

解法I - 位运算判定

在231. Power of Two中，我们判定了一个数是2的幂。

一个数如果是4的幂，则肯定是2的幂，同时，它的二进制中，仅存在的唯一一个1，则必须在二进制的第2，4，6，8，10…等偶数位上

也就是n与0b0101 0101 0101 0101 0101 0101 0101 0101做位与（&）操作，最终的结果不为0；如果为0则说明1不在偶数位上。

实现

class Solution {
  public boolean isPowerOfFour(int num) {
    return (num > 0) && ((num & (num - 1)) == 0) && ((num & 0x55555555) != 0);
  }
}

解法II - 余数判定

如果在面试过程中，想不到num & 0x55555555 == 0这个操作，也可以从另一个角度思考。

一个数如果已经是2的幂，那么它满足什么条件就可以变成4的幂呢？

显然，当n - 1能被3整除的时候，他就一定是4的幂。

实现

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