342. Power of Four

题目描述和难度

  • 题目描述:

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

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

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

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

思路分析

求解关键:

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