231-2的幂

LeetCode 231. Power of Two

Given an integer n, return true if it is a power of two. Otherwise, return false.

An integer n is a power of two, if there exists an integer x such that $n = 2^x$.

Example 1:

Input: n = 1
Output: true
Explanation: 20 = 1

Example 2:

Input: n = 16
Output: true
Explanation: 24 = 16

method 1: 位运算

整型int的范围是：$-2^{31} \sim 2^{31} - 1$
所以最大的2次幂是$2^{30}$
如果一个数是2次幂，那他肯定可以被最大的2次幂$2^{30}$整除，所以就用这个条件来判断

• 2的n次幂就是1左移n位1 << n

bool isPowerOfTwo(int n) {
    return n > 0 && ((1 << 30) % n == 0);
}

---

method 2:

• x & -x可以得到x最低位的1以及后面若干个0

如果一个数是2的幂，那肯定只含有1个1，比如8是0000 1000

所以如果是2的幂，x & -x的值肯定跟原来一样，不是2的幂肯定含有多个1，x & -x的值会比原来小

bool isPowerOfTwo(int n) {
    return n > 0 && ((n & -n) == n);
}