GuilinDev

Lc0231

05 August 2008

231 - Power of Two

原题概述

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

Example 1:

1
2
3

Input: 1
Output: true 
Explanation: 20 = 1

Example 2:

1
2
3

Input: 16
Output: true
Explanation: 24 = 16

Example 3:

1
2

Input: 218
Output: false

题意和分析

判断一个是否是2的幂，这道题自然可以用recursive或者iterative来做(O(log n))，

也可以用n & (n - 1),

  • n = 2 ** 0 = 1 = 0b0000…00000001, and (n - 1) = 0 = 0b0000…0000.
  • n = 2 ** 1 = 2 = 0b0000…00000010, and (n - 1) = 1 = 0b0000…0001.
  • n = 2 ** 2 = 4 = 0b0000…00000100, and (n - 1) = 3 = 0b0000…0011.
  • n = 2 ** 3 = 8 = 0b0000…00001000, and (n - 1) = 7 = 0b0000…0111.

因此我们看出，如果n是2的方幂，二者刚好位数全部不一样，那么做与操作n & (n-1) == 0b0000…0000 == 0；

否则比如 n =14 = 0b0000…1110, and (n - 1) = 13 = 0b0000…1101，n & (n-1) == 0b0000…1100 != 0.

另外n当然不能是0或负数。

Time O(1) ：Space：O(1)；

代码

迭代

1
2
3
4
5
6
7
8
9
10
11

class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n <= 0) {
            return false;
        }
        while (n % 2 == 0) {
            n /= 2;
        }
        return n == 1;
    }
}

递归

1
2
3
4
5
6
7
8
9
10
11

class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n == 1) {
            return true;
        } else if (n <= 0 || n % 2 != 0) {
            return false;
        } else {
            return isPowerOfTwo(n / 2);
        }
    }
}

若 n = 2^x，且 x 为自然数（即 n 为 2 的幂），则一定满足以下条件：

恒有 n & (n - 1) == 0，这是因为：

  • n 二进制最高位为 1，其余所有位为 0；
  • n - 1 二进制最高位为 0，其余所有位为 1；
  • 此外，一定满足 n > 0。

因此，通过 n > 0 且 n & (n - 1) == 0 即可判定是否满足 n = 2^x。

1
2
3
4
5

class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && ((n & (n - 1)) == 0);
    }
}
This site is open source. Improve this page.