342. Power of Four

 

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example 1:

Input: 16
Output: true

Example 2:

Input: 5
Output: false

Follow up: Could you solve it without loops/recursion?

Credits:
Special thanks to @yukuairoy for adding this problem and creating all test cases.

 

这道题让我们判断一个数是否为4的次方数,那么最直接的方法就是不停的除以4,看最终结果是否为1,参见代码如下:

 

解法一:

class Solution {
public:
    bool isPowerOfFour(int num) {
        while (num && (num % 4 == 0)) {
            num /= 4;
        }
        return num == 1;
    }
};

 

还有一种方法是跟 Power of Three 中的解法三一样,使用换底公式来做,讲解请参见之前那篇博客:

 

解法二:

class Solution {
public:
    bool isPowerOfFour(int num) {
        return num > 0 && int(log10(num) / log10(4)) - log10(num) / log10(4) == 0;
    }
};

 

下面这种方法是网上比较流行的一种解法,思路很巧妙,首先根据 Power of Two 中的解法二,我们知道 num & (num - 1) 可以用来判断一个数是否为2的次方数,更进一步说,就是二进制表示下,只有最高位是1,那么由于是2的次方数,不一定是4的次方数,比如8,所以我们还要其他的限定条件,我们仔细观察可以发现,4的次方数的最高位的1都是计数位,那么我们只需与上一个数 (0x55555555) <==> 1010101010101010101010101010101,如果得到的数还是其本身,则可以肯定其为4的次方数:``

 

解法三:

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

或者我们在确定其是2的次方数了之后,发现只要是4的次方数,减1之后可以被3整除,所以可以写出代码如下:

 

解法四:

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

 

类似题目:

Power of Three

Power of Two

 

参考资料:

https://leetcode.com/problems/power-of-four/

https://leetcode.com/problems/power-of-four/discuss/80457/Java-1-line-(cheating-for-the-purpose-of-not-using-loops)

https://leetcode.com/problems/power-of-four/discuss/80460/1-line-C%2B%2B-solution-without-confusing-bit-manipulations

 

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation