【Leetcode】231.2的幂

231 2的幂

题目：
给定一个整数，编写一个函数来判断它是否是 2 的幂次方。

方法一：

一直除2看最后得到的是否为1，这种方法的时间复杂度为O(logn)。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean isPowerOfTwo(int n) {
        if(n <= 0)
            return false;
        if(n == 1)
            return true;
        while(n % 2 == 0){
            n = n / 2;
            if(n == 1)
                return true;
        }
        return false;
    }
}

方法二(位运算)：

所有为2的幂的整数，其二进制均是除了其有效最高位以外全是0的数。也就是说，我们只需要判断这个数是否有除了有效最高位之外还有没有其他的1即可。

这里可以用到一个位运算小技巧：给定一个数n，将n和(n-1)做一次与运算，即可将n的最后一位1去掉。例如9和8，即1001 & 1000 = 1000，把最后一位的1去掉。再例如12和11，即1100 & 1011 = 1000，最后一位的1被去掉。

那么对于所有2的幂，我们将它与它-1后的数做一次与运算，就会将其唯一一位1消去，最后等于0。

1
2
3
public boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

时间复杂度和空间复杂度都为O(1)