[LeetCode] Power of Two

Power of Two

Given an integer, write a function to determine if it is a power of two.

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

解题思路:

这道题的题意是判断一个数是不是2的幂。有几个问题需要确定一下:

1、1也是2的幂,是0次幂

2、将一个整数向左移一位,相当于这个整数乘以2,向右移一位,相当于该整数除以2

3、注意大整数的溢出情况。

下面是代码:

class Solution {
public:
    bool isPowerOfTwo(int n) {
        long long num = 1;
        while(num <= n){
            if(num==n){ //先判断,考虑到1的情况
                return true;
            }
            num = num << 1;
        }
        return false;
    }
};

update in 2015-07-08

感谢网友的提出新的方法。上述方法的时间复杂度为:O(logn)。有没有更快的方法?注意到2的幂的倍数的二进制有一个特点,最高位为1,其余位为零。于是可以判断某个数的二进制表示是否只有一个1,若只有一个1,则为2的幂,否则不是。对于正整数,n&(n-1)表示去除n的二进制表示的最后一个1,若n&(n-1)==0,则n为2的幂。

注意对于0和负数,都不是2的幂。此方法的时间复杂度为O(1)。

class Solution {
public:
    bool isPowerOfTwo(int n) {
        if(n<=0){
            return false;
        }
        return (n&(n-1))==0;
    }
};


0 条评论

    发表评论

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