题目

难度：★☆☆☆☆
类型：数学

给定一个整数 (32 位有符号整数)，请编写一个函数来判断它是否是 4 的幂次方。

进阶：
你能不使用循环或者递归来完成本题吗？

示例

示例 1:
输入: 16
输出: true

示例 2:
输入: 5
输出: false

解答

这道题与【题目231. 2的幂】和【题目326. 3的幂】属于同一题型，递归和迭代的方法可以直接查看【题目231. 2的幂】，这里介绍两种其他方法。

方案1：转二进制

将输入数字转为二进制数，如果输入数字是4的幂，那么转为二进制数后，最高位一定是“1”，除最高位外的所有位均为“0”，且零的个数是2的非负整数倍。这里在编码时这样实现：

1. 将输入数字转为二进制，进而转为字符串；

2. 满足以下所有条件时，输入数字是4的幂：
   （1）二进制数的最高位为“1”；
   （2）二进制数的其他位均为“0”或者空（次数输入数字为1）；
   （3）二进制数的其他位中“0”的个数是2的整数倍。

class Solution(object):
    def isPowerOfFour(self, num):
        """
        :type num: int
        :rtype: bool
        """
        bin_str = bin(num)[2:]

        return bin_str[0] == '1' and set(bin_str[1:]).issubset({'0'}) and bin_str.count('0') % 2 == 0

方案2：除以3的余数

首先，4的幂一定是2的幂，因此可以先通过（n and n & (n-1) == 0）筛选出2的幂，与其他2的幂不同的是，任何4的幂与1的差值均为3的倍数。

证明：
假设我们当前研究的数是4的幂。

证明是3的倍数，例如64 - 1 = 3 * 16 + 3 * 4 + 3 * 1 = 65。

class Solution(object):
    def isPowerOfFour(self, num):
        """
        :type num: int
        :rtype: bool
        """
        return num & (num-1) == 0 and (num-1) % 3 == 0

如有疑问或建议，欢迎评论区留言~