342. Power of Four

题目描述和难度

题目描述：

给定一个整数 (32位有符整数型)，请写出一个函数来检验它是否是4的幂。

示例:
当 num = 16 时，返回 true 。当 num = 5时，返回 false。

问题进阶：你能不使用循环/递归来解决这个问题吗？

致谢:
特别感谢 @yukuairoy 添加这个问题并创建所有测试用例。

题目难度：简单。
英文网址：342. Power of Four 。
中文网址：342. 4的幂。

思路分析

求解关键：

1、列出 $4^1$、$4^1$、$4^2$、$4^3$ 等等，找出规律；

$4^1 = 2^2 = 2^2$，表示成二进制就是 $100$，$1$ 后面 $2$ 个“$0$”；
$4^2 = (2^2)^2 = 2^4$，表示成二进制就是 $10000$，$1$ 后面 $4$ 个“$0$”；
$4^3 = (2^2)^3 = 2^6$，表示成二进制就是 $1000000$，$1$ 后面 $6$ 个“$0$”；
$4^4 = (2^2)^4 = 2^8$，表示成二进制就是 $100000000$，$1$ 后面 $8$ 个“$0$”；
$4^5 = (2^2)^5 = 2^10$，表示成二进制就是 $10000000000$，$1$ 后面 $10$ 个“$0$”。

2、如果是负数，直接返回 false； 3、使用位运算的与运算去做判断； 4、不要忘记转换成二进制以后，后面跟的 0 是偶数，所以原来的位数一定是奇数。

下面的解法是从讨论区看来的。

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

简单解释一下： 1、num > 0 很好理解，4 的整数方幂一定是正数；
2、num & (num - 1) 这个运算能够将 num 二进制表示中最右边的那个 "1" 变成 "0"，根据 4 的方幂的二进制表示的特点，这个数一定只有一个数位上是“1”，并且这个数位是最高位，因此 num & (num - 1) 一定是 0；
3、在满足只有最高位是 1 的前提下， $num - 1$ 全部数位上只有 1 (并且是偶数个)，并且每隔两个数位一定可以提取公因式，且一定会有因子 "11"（十进制为 3 ），因此一定可以提取出公因子 3，例如二进制数 $111111$ ，本来可以表示成：

$$ (111111)_2 = 1 \times 2^5 + 1 \times 2^4 + 1 \times 2^3 + 1 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 $$

其中 $1 \times 2^3 + 1 \times 2^2$ 可以表示成：

$$ 1 \times 2^3 + 1 \times 2^2 = 2^2 \times (1 \times 2^1 + 1 \times 2^0 ) $$

其中 $1 \times 2^5 + 1 \times 2^4$ 可以表示成：

$$ 1 \times 2^5 + 1 \times 2^4 = 2^2 \times (1 \times 2^3 + 1 \times 2^2 ) $$

这种做法可以递归下去，得到

$$ (111111)_2 = 1 \times 2^5 + 1 \times 2^4 + 1 \times 2^3 + 1 \times 2^2 + (1 \times 2^1 + 1 \times 2^0) $$

$$ (111111)_2 = 2^2 \times [2^2 \times (1 \times 2^1 + 1 \times 2^0)] + 2^2 \times (1 \times 2^1 + 1 \times 2^0) + (1 \times 2^1 + 1 \times 2^0) $$

$$ (111111)_2 = [2^2 \times 2^2 + 2^2 + 1] \times (1 \times 2^1 + 1 \times 2^0) $$

$$ (111111)_2 = [2^2 \times 2^2 + 2^2 + 1] \times 3 $$

以上的 3 个条件均为一个整数为 4 的方幂的必要条件，因此它们同时成立就成为了充分必要条件了。

参考解答

参考解答1：使用循环进行判断。

public boolean isPowerOfFour(int num) {
    if (num <= 0) {
        return false;
    }
    while (num % 4 == 0) {
        num /= 4;
    }
    return num == 1;
}

参考解答2：观察 4 的方幂的二进制表示的特点。

public class Solution {

    public boolean isPowerOfFour(int num) {
        if (num <= 0) {
            return false;
        }
        String binaryString = Integer.toBinaryString(num);
        // System.out.println(binaryString);
        int len = binaryString.length();
        return len % 2 == 1 && (num & 1 << (len - 1)) == num;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        boolean powerOfFour = solution.isPowerOfFour(-2147483648);
        System.out.println(powerOfFour);
    }
}

参考解答3：充分挖掘数学性质。

public class Solution2 {

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

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0342-power-of-four ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。