鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 编程语言开发 > erlang > >

【一天一道LeetCode】#342. Power of Four

来源:互联网 作者:佚名 时间:2016-07-17 21:13
一天一道LeetCode 本系列文章已全部上传至我的github,地址:ZeeCoder‘s Github 欢迎大家关注我的新浪微博,我的新浪微博 欢迎转载,转载请注明出处 (一)题目 Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

一天一道LeetCode

本系列文章已全部上传至我的github,地址:ZeeCoder‘s Github
欢迎大家关注我的新浪微博,我的新浪微博
欢迎转载,转载请注明出处

(一)题目

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

Example:
Given num = 16, return true. Given num = 5, return false.

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

(二)解题

题目大意:判断一个数是不是4的n次方数。
解题思路:可以参考:【一天一道LeetCode】#326. Power of Three和【一天一道LeetCode】#231. Power of Two
首先,最简单的方法,采用循环来做:

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

题目中有提问说能不能不用循环和递归来做,和判断3的n次方数一样,4的n次方数在整形数内只有16个,很快就能列举出来,也不失为一个好办法。
另外观察4的n次方数和2的n次方数,可以看出,2的n次方数中能开方得到整数的均为4的n次方数。

class Solution {
public:
    //三个条件:大于0,是2的n次方数,开方后得到整数
    bool isPowerOfFour(int num) {
        return (num>0)&&!(num&(num-1))&&(sqrt(num)*sqrt(num)==num);
    }
};

在leetcode的讨论区看到这样一个答案,很巧妙。
首先判断num是不是2的n次方数,在判断他与0xaaaaaaaa相与是否为0。
4的n次方数有一个特点就是,在bit位上,第0,2,4,6,8,10….位上为1,
所以,先判断是不是3的n次方数,就保证了有且仅有一位上为1的数,然后在剔除奇数位上为1的数,剩下的就是4的n次方数了。

class Solution {
public:
    bool isPowerOfFour(int num) {
        //三个条件:大于0,是2的n次方数,有且仅有偶数位上为1
        return (num>0)&&!(num&(num-1))&&!(num&0xaaaaaaaa);
    }
};
网友评论
<