目录

原题：2的幂

方法一：位运算

 方法二：判断n是否为最大2的幂的约数

总结 

【声明】：这是一道关于位运算的题目哦，只不过不像原来那么死板，之后的题目中出现一题多解情况是很正常的事情哦。这里，麻烦大家先将原来关于位运算的基础知识点再过一遍。

蓝桥杯算法竞赛系列第一章——位运算的奇巧淫技及其实战_安然无虞的博客-CSDN博客

【前言】今天是第一次LeetCode刷题打卡哦，铁汁们都到了咩，准备上车咯。

原题：2的幂

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

示例1：

  

   

    

     

    
    

     

      输入：n = 1
     
    
   

    

     

    
    

     

      输出：true
     
    
   

    

     

    
    

     

      解释：20 = 1
     
    
  
 

 示例2：

  

   

    

     

    
    

     

      输入：n = 3
     
    
   

    

     

    
    

     

      输出：false
     
    
  
 

思考：本题除了利用位运算解决，还有没有别的方法了？

方法一：位运算

整数n是2的幂，则一定满足两个条件：

• 恒有n & (n - 1) == 0
• 一定满足 n > 0

解释：1、为什么说n是2的幂就恒有n & (n - 1) == 0 呢，因为n的二进制最高位是1，其余位是0；(n - 1)的二进制最高位是0，其余位是1

注意：这里所说的最高位不是理论上的最高位，什么是理论上的最高位呢？

  

   

    

     

    
    

     

      //整数2：
     
    
   

    

     

    
    

     

      00000000 00000000 00000000 00000010
     
    
  
 

它的理论上的最高位是最左边的0，通常我们也叫它符号位。

但是我们在实际操作当中，不会去把32位上面每一位的数字都写出来，就好比：

  

   

    

     

    
    

     

      //整数2：
     
    
   

    

     

    
    

     

      10
     
    
  
 

直接用10就代表2的二进制表示形式了。所以它的最高位就是1了，这个也就是我这里所说的“最高位”的意思。

2、为什么说n > 0 呢？因为2的幂一定是大于0的，如果不加上程序就执行不过去了。你看：

  

   

    

     

    
    

     

      bool isPowerOfTwo(int n){
     
    
   

    

     

    
    

     
    return n & (n - 1) == 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

执行结果：

虽然通过了绝大部分测试用例，但是还是少考虑了个别边界，所以一定要注意哦。

代码执行：

  

   

    

     

    
    

     

      bool isPowerOfTwo(int n){
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    if(n > 0 && (n & (n - 1)) == 0){
     
    
   

    

     

    
    

     
        return true;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    return false;
     
    
   

    

     

    
    

     

      }
     
    
  
 

不过这里其实是可以简化代码的，将上面的三行代码化为一行： 

  

   

    

     

    
    

     

      bool isPowerOfTwo(int n){
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    return n > 0 && ((n & (n - 1)) == 0);
     
    
   

    

     

    
    

     

      }
     
    
  
 

 【敲黑板】：铁汁们一定要注意优先级，没有必要说把每一个运算符优先级都记住，反正我是记不住，也不会花时间去记它，当我们不确定的时候加上括号就行了，注意一定要学会加括号哦，可能因为你少加或者是多加一个括号程序都会报错！

执行结果：

  

   

    

     

    
    

     

      ​
     
    
   

    

     

    
    

     

      ​通过
     
    
   

    

     

    
    

     

      执行用时：0 ms, 在所有 C 提交中击败了100.00%的用户
     
    
   

    

     

    
    

     

      内存消耗：5.3 MB, 在所有 C 提交中击败了83.80%的用户通过测试用例：1108 / 1108
     
    
  
 

好，这题其实很明显是用位运算解决的，但是再仔细想想有没有别的方法了呢？其实是有的...

 方法二：判断n是否为最大2的幂的约数

除了利用位运算外，还有一种比较取巧的方法：

在题目给定的32位有符号整数的范围内，最大的2的幂为2 ^ 30 = 1073741824。我们只需要判断 n 是不是 2 ^ 30的约数即可。 

这里我们补充一下有符号整数和无符号整数的范围：

有符号整数：int :32位,最高位是符号位，剩下31位是数值位，所以取值范围是 -（2 ^ 31） ~ 2 ^ 31 - 1 ,即为 -2147483648 ~ 2147483647（20亿）

无符号整数：unsigned int:32位，没有符号位，32位全部是数值位，所以取值范围是2 ^ 32 - 1,即为4294967295（40亿）

大家知道这个概念就好做了。

代码执行：

  

   

    

     

    
    

     

      bool isPowerOfTwo(int n){
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    int Big = 1 << 30;//扩大至 2 ^ 30
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    return n > 0 && (Big % n == 0);
     
    
   

    

     

    
    

     

      }
     
    
  
 

执行结果：

  

   

    

     

    
    

     

      通过
     
    
   

    

     

    
    

     

      执行用时：0 ms, 在所有 C 提交中击败了100.00%的用户
     
    
   

    

     

    
    

     

      内存消耗：5.3 MB, 在所有 C 提交中击败了90.46%的用户通过测试用例：1108 / 1108
     
    
  
 

总结 

• 今天是力扣打卡第一天！笔者非常兴奋！！
• 前期的话，因为题目比较简单，笔者主要采用C语言编写程序，到了中后期，就会采用C，C++解题
• 今天的刷题你是否有所收获呢，欢迎评论区留言点评，咱们明天再见！

文章来源: bit-runout.blog.csdn.net，作者：安然无虞，版权归原作者所有，如需转载，请联系作者。

原文链接：bit-runout.blog.csdn.net/article/details/121051428