Zhenhua's Wiki 231. Power of Two

231. Power of Two

Leetcode Math Bit Manipulation

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

Example 1:

Input: 1
Output: true 
Explanation: 2⁰ = 1

Example 2:

Input: 16
Output: true
Explanation: 2⁴ = 16

Example 3:

Input: 218
Output: false

分析¶

2的幂。判断一个整数 $n$ 是否是2的幂，最直接的方法就是不断除以2，看余数是否是1。但需要注意 $n=1$ 时，虽然1除以2的余数是1，但是它是2的幂。注意应该使用右移运算(n >>> 1)，而不是除法(n/2)，因为位运算比除法快得多。

使用递归的代码：

public boolean isPowerOfTwo(int n) {
    if (n <= 0) return false;
    if (n == 1) return true;
    if (n % 2 != 0) return false;
    return isPowerOfTwo(n >>> 1);
}

使用迭代的代码：

public boolean isPowerOfTwo(int n) {
    if (n <= 0) return false;
    while (n > 1) {
        if (n % 2 == 1) return false;
        n >>= 1;
    }
    return n == 1 ? true : false;
}

仔细思考一下如果一个数是2的幂的话，它的二进制表示有什么特点？有且只有一个数是1，其他都是0。利用此特点，一一检查 $n$ 的二进制表示：有且只有一个1。于是就可以用LeetCode 191. Number of 1 Bits中描述的所有方法。

public boolean isPowerOfTwo(int n) {
    if (n <= 0) return false;
    while ((n != 0) && ((n & 1) != 1))
        n >>= 1;
    n >>= 1;
    return n == 0; 
}

使用 $n&(n-1)$ 技巧：

public boolean isPowerOfTwo(int n) {
    if (n <= 0) return false;
    return (n & (n - 1)) == 0; 
}