Leetcode | 2的幂

[techiall]

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

示例 1:

输入: 1
输出: true
解释: 20 = 1

示例 2:

输入: 16
输出: true
解释: 2^4 = 16

示例 3:

输入: 218
输出: false

java

使用位运算。

我们对特殊情况先进行判断，小于等于 0 的肯定不是，等于 1 的肯定是 true 。

对于一般情况。如果该数为 2 的幂，最高位为 1，其他位为 0 。

8       ->  0000 1000
16      ->  0001 0000
32      ->  ‭0010 0000‬
64      ->  0100 0000‬
...

对于 2 ^ n - 1 的数。

7       ->  0000 0111
15      ->  0000 1111
31      ->  ‭0001 1111
63      ->  0011 1111
...

两者进行与运算（&）。

8       ->  0000 1000
7       ->  0000 0111
&       ->  0000 0000

16      ->  0001 0000
15      ->  0000 1111
&       ->  0000 0000

32      ->  ‭0010 0000‬
31      ->  ‭0001 1111
&       ->  0000 0000

64      ->  0100 0000‬
63      ->  0011 1111
&       ->  0000 0000

14      ->  0000 1110
13      ->  0000 1101
&       ->  0000 1100
...

因此，我们只需要把这个数和比他小 1 的数进行与运算

你会发现得出的结果是 0 的，都是 2 的幂次

与运算之后不是 0 的就不是 2 的幂次

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