231. 2的幂

• 判断一个数是否为 2 的幂次

• 暴力算法

  // 自己想的
  // 一个数如果为2的幂次 那么在无限除2之后 等于 1
  class Solution{
      public boolean isPowerOfTwo(int n){
          while (true){
              if (n / 2 == 1){
                  return true;
              }
              // 此时涉及到边界条件
              // 如果n<=0,那么程序无限循环
              // 同时n为非幂 应该返回false
              if (n <=0 || (n % 2 != 0){
                  return false;
              }
              n /= 2;
          }
      }
  }
  // 主要问题在于 n<=0 这个边界条件没有
  

• 思考后 如果n为2的幂 那么在二进制的形式中 n必然第一位为0 其他位置有且仅有一个1 那么考虑如何获取这个1

  // 官方做法
  // 1. 利用 按位& 运算，n & (n - 1)会剔除掉 n 在二进制里面的最小一位1
  // 因为 n-1 是相当于 在最小一位1前面的数不变  0ba10000 - 1 = 0ba01111, 所以按位想与后为 0ba00000; 这样判断结果为0就可以了
  
  class Solution{
      public boolean isPowerOfTwo(int n){
          return ((n > 0) || ((n & (n - 1)) == 0);
      }
  }
  
  // 2. 同样利用 按位&
  // n & (-n) 可以获得最低的1
  // -n 是 n 的二进制数 所有数取反+1
  class Solution{
      public boolean isPowerOfTwo(int n){
          return ((n > 0) || ((n & -n) == n);
      }
  }
  

• 官方做法主要考察的就是 按位& 的计算过程 及 一个数的负数二进制是什么样的