231. Power of Two

39.6%

https://leetcode.com/problems/power-of-two/#/description

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

方法一：

利用 n&(n-1)判断，时间复杂度O(1)

值得关注的点， 1. 考虑n<=0的情况 2. n&(n-1)为0时是True，所以要加否定 3. 否定符号是 ! 不是 ~

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

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && !(n&(n-1));
    }
};

方法二：

相除法，时间复杂度O(1)

1	return n>0 && (1073741824 % n == 0);

方法三：

迭代，时间复杂度 O(logn)

1
2
3

if(n==0) return false;
while(n%2==0) n/=2;
return (n==1);

方法四：

递归，时间复杂度O(logn)

1	return n>0 && (n==1 \|\| (n%2==0 && isPowerOfTwo(n/2)));

Python one line solution

class Solution(object):
    def isPowerOfTwo(self, n):
        """
        :type n: int
        :rtype: bool
        """
        return n > 0 and not (n & n-1)

参考资料：