2. 判断一个整数是否是 2 的幂次方

川长思鸟来 2024-03-30 11:49 91阅读 0赞

#### 文章目录 ####

*   *  题目
     *  解题思路
     *  解法一：获取二进制最低位
     *   *  代码实现
         *  复杂度分析
     *  解法二：删除二进制最低位
     *   *  代码实现
         *  复杂度分析
     *  解法三：JDK Integer.bitCount(n)
     *   *  代码实现
         *  复杂度分析

### 题目 ###

> 给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 `true` ；否则，返回 `false` 。 如果存在一个整数 `x` 使得 `n == 2^x`，则认为 n 是 2 的幂次方。题目来自[leetcode][]

### 解题思路 ###

如果一个数是2的幂次方，那么这个整数肯定满足两个条件：

1.  大于0
2.  二进制表达中，有且只有1个位置为1。

<table> 
 <thead> 
  <tr> 
   <th>n</th> 
   <th>二进制表达</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>2^0 == 1</td> 
   <td>0001</td> 
  </tr> 
  <tr> 
   <td>2^1 == 2</td> 
   <td>0010</td> 
  </tr> 
  <tr> 
   <td>2^2 == 4</td> 
   <td>0100</td> 
  </tr> 
  <tr> 
   <td>2^3 == 8</td> 
   <td>1000</td> 
  </tr> 
  <tr> 
   <td>…</td> 
   <td>…</td> 
  </tr> 
  <tr> 
   <td>2^n</td> 
   <td>第n位为1，其他均为0。n从0开始。</td> 
  </tr> 
 </tbody> 
</table>

### 解法一：获取二进制最低位 ###

我们首选可以排除`<=0`的整数，然后可以使用获取二进制最低位的方式去判断`>0`的整数，我们知道获取最低位的方法是 `n & (-n)`，因为要求n只能包含一个1，所以势必 `n = n & (-n)`。

#### 代码实现 ####

class Solution {
        
        public boolean isPowerOfTwo(int n) {
        
            if(n <= 0){
        
                return false;
            }
            // 只有一个位为1，所有lowbit 应该等于n本身
            return (n & -n) == n;
        }
    }

#### 复杂度分析 ####

时间复杂度:  O ( 1 ) O(1) O(1)。  
空间复杂度:  O ( 1 ) O(1) O(1)。

### 解法二：删除二进制最低位 ###

解题思路同解法一，然后我们将获取最低位改为删除最低位，因为n的二进制表示中有且只有1个1，那么删掉最后一个1之后剩下的应该都是0才对，即 `(n & (n - 1)) == 0`。

#### 代码实现 ####

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

#### 复杂度分析 ####

时间复杂度:  O ( 1 ) O(1) O(1)。  
空间复杂度:  O ( 1 ) O(1) O(1)。

### 解法三：JDK Integer.bitCount(n) ###

解题思路还是获取二进制中1的个数，我们可以使用JDK自带方法 `Integer.bitCount(n)` 去获取1的个数，为1则返回`true`，否则返回`false`。

#### 代码实现 ####

class Solution {
        
        public boolean isPowerOfTwo(int n) {
        
            if(n <= 0){
        
                return false;
            }
            return Integer.bitCount(n) == 1 ? true : false;
        }
    }

#### 复杂度分析 ####

时间复杂度  O ( l o g N ) O(logN) O(logN)：N为二进制位数。参见[1.位1的个数][1._1]  
空间复杂度  O ( 1 ) O(1) O(1)。

[leetcode]: https://leetcode.cn/problems/power-of-two/description/
[1._1]: https://blog.csdn.net/justyuze/article/details/128403315