leetcode Question: Power of Two

Power of Two

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

Analysis:

An straightforward way is to keep doing "divide by 2" for the number and check if current number "mod 2" is zero. However this is pretty slow (it still can pass the OJ).

More efficient way is to use bit manipulation.

If one number is a power of 2, then its binary must starts with 1 and all the lower bits are 0. e.g.,
2 10
4 100
8 1000
16 10000
...

Also, we have to find a "mask" to check this format, what "mask" should we use?
Let's see some examples:
1 01
3 011
7 0111
15 01111
...

Well, it is not hard to see that,  if one number "n" is a power of 2, then "n-1" must have all 1s in its binary format. Therefore, "n & n-1" must be 0.  

Code(C++):

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

Code(Python):

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