342. Power of Four 「4 的幂」

给定一个整数(有符号 32 位),编写一个函数检查其是否是 4 的幂。

例一:
输入: 16
输出: true

例二:
输入: 5
输出: false

这个题和之前判断 2 的幂的题很像,变成了 4 的幂。之前的方法对于这个题来说就有些不够用了,我们需要再多想一下。

这里用到了一个小技巧,从 LeetCode 评论区学来的。既然已经有方法可以知道是否是 2 的幂了,我们接下来就判断这个二进制中唯一的 1 的位置就好了。如果用一些循环去判断,可能稍微有些麻烦,干脆直接提前构造好一个特殊的数字,用这个数字去判断是否是 4 的幂。这个数字就是 0xAAAAAAAA。为什么是它呢,把它写成二进制就好理解了 10101010 10101010 10101010 10101010,只要是 4 的幂与这个特殊的数字与,结果便为 0。或者是和 0x55555555 与,结果为自身。

/*
 * 342. Power of Four
 * https://leetcode.com/problems/power-of-four/
 * https://www.whosneo.com/342-power-of-four/
 */

public class IsPowerOfFour {
    public static void main(String[] args) {
        IsPowerOfFour solution = new IsPowerOfFour();

        System.out.println(solution.isPowerOfFour(36));
        System.out.println(solution.isPowerOfFour(64));
        System.out.println(solution.isPowerOfFour(32));
        System.out.println(solution.isPowerOfFour(128));
    }

    private boolean isPowerOfFour(int num) {
        return num > 0 && (num & (num - 1)) == 0 && (num & 0xAAAAAAAA) == 0;
    }
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注