【LeetCode】2的幂

原题信息如下所示：

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

如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。

n的取值范围：-2^31 <= n <= 2^31-1




输入：n = 1
输出：true
解释：20 = 1
输入：n = 16
输出：true
解释：24 = 16
输入：n = 3
输出：false

看到这个题的第一想法是什么呢？

1、判断是不是2的幂，那不就是判断这个数能不能被2整除嘛

2、使用循环做除以2的操作，终止条件：商为0，

3、除法期间，判断余数是不是1，如果出现1，那么这个数就不能被2整除了

4、没有出现1，那么就是2的幂

代码：

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

• 时间复杂度为 O(logn)
  
• 空间复杂度为O(1)
  

这样也不是不能解决问题，那么我们能不能不用循环呢？

在leetcode官解中看到一个取巧的方法，从 n 的取值，可以看出最大值为 2^31-1，那么2的幂最大值则为 2^30，也就表示用 2^30 去除以 n ，余数为0，这个数就是2的幂

代码：

static final int BIG = 1 << 30;
public boolean isPowerOfTwo(int n) {
  return n > 0 && BIG % n == 0;
}

• 时间复杂度：O(1)。
  
• 空间复杂度：O(1)。
  

那么是不是还有更更更加优雅的解法呢？

这还真的有！

可以使用二进制，一个数是2的幂，那么这个数转化成二进制以后，这里面一定只有一个1，其余位数全是0。

我们可以利用一下这个特点，假如我们把这个1去掉，然后判断其他位是不是0就可以了

我们可以使用位运算，使用 & 按位运算：n & (n-1)

4 转化成二进制是 0100，当4做减一操作以后，二进制数变成了0011，这时候进行 & 操作，最后的结果一定是 0 。

如果一个数不是2的幂，那么转化成二进制以后，里面最少有 2 个1的存在，例如 5 转化成二进制位 0101，当 5 做减一操作以后，二进制数变成了0100，这个数跟原数进行按位与操作，因为最高位上的1没有改变，所以结果不是0

代码

public boolean isPowerOfTwo(int n) {
  return n > 0 && (n & (n - 1)) == 0;
}

• 时间复杂度：O(1)。
  
• 空间复杂度：O(1)。
  

负数的补码在计算机中是按照补码的方式存储的，然后你想想这个是不是也可以优雅的操作一波呢？

另外在leetcode评论区看到一个更有趣的解法，你来品一品～

END

这个题不难，官方给出的是简单类型，暴力解法也不会超时，但是却有更加优雅的方式。

第一次看到这个题目的时候，想到了转化二进制，却没有想到二进制的运算，对计算机中的二进制的知识还有欠缺，对原码、反码、补码了解不多，看来做算法题还需要加强这方面的训练。