前言说明
算法学习，日常刷题记录。
题目连接
题目内容
给你一个整数n，请你判断该整数是否是2的幂次方。如果是，返回true；否则，返回false。
如果存在一个整数x使得n == 2x ，则认为n是2的幂次方。
示例1:
输入：n = 1
输出：true
解释：20 = 1
示例2:
输入：n = 16
输出：true
解释：24 = 16
示例3:
输入：n = 3
输出：false
示例4:
输入：n = 4
输出：true
示例5:
输入：n = 5
输出：false
提示:
-2^31 <= n <= 2^31 - 1
进阶:
你能够不使用循环/递归解决此问题吗？
分析过程
方法1
首先我们想到最直观的方法，用循环来解决，若一个数是2的幂，必定是2的倍数，而且除以2后还是2的倍数，再除以2循环下去，最后会变成1。但是如果这个数不是2的幂，即使这个数是2的倍数，也不是所有的因子都会是2，所以除以2到最后不会变成1。
class Solution {
public boolean isPowerOfTwo(int n) {
if (n < 1) {
// 2的幂必定大于等于1，若小于1，直接判定为不是
return false;
}
// 若一个数是2的幂，必定是2的倍数，而且除以2后还是2的倍数，再除以2，直到最后为1，如果最后不是1，那么证明这个数虽然是2的倍数，但是不是所有因子都是2，所以不是2的幂
while (n % 2 == 0) {
n /= 2;
}
// 最后一步判断是否为1，若是1，则证明n是2的幂，若不是1，则证明n不是2的幂
return n == 1;
}
}
提交代码后，执行用时1ms，时间击败100.00%的用户，内存消耗35.4MB，空间击败74.67%的用户。
方法2
俗话说，学好数理化，走遍天下都不怕。对于算法，俗话也说，学好位运算，刷遍题目都不怕！
看到有点feel的算法题，要先想想能不能用位运算解决。
先来枚举几个2的幂，看看他们的二进制位长什么样。
我们可以发现二进制的幂首先大于等于1，然后除了2的0次幂是1外，其他的2的n次幂，都是只有一个1的位。那么问题就转化成了，如何判断这个数的二进制位只有一个1。
我们拍脑袋就能想到肯定是通过位运算来实现的，那么我们先来找一个例子，例如2的2次幂等于4，二进制表示就是"0100"，我们再看4-1=3，3的二进制表示就是"0011"，如果两者进行并运算&，那么就会得到二进制"0000"，也就是0；如果是5，二进制表示"0101"，那么5-1=4，4的二进制表示"0100"，如果两者进行并运算&，那么就会得到二进制"0100"，所以说一个数和这个数减1进行并运算，即n&(n-1)，结果是这个数被去掉最右边的1。
我们上面知道在大于1的整数中，2的幂的二进制位只有一个1，所以我们只需要判断n&(n-1)是否等于0即可，因为2的幂只有一个1，通过&并运算后，会去掉最右边的1，那么二进制位就全部都是0，如果二进制位不全部是0，那么这个数就不是2的幂。
所以这样一来，是不是变得很简单了？一行代码即可解决。
class Solution {
public boolean isPowerOfTwo(int n) {
// 2的幂肯定大于等于1，然后通过类似计算汉明距离的方法用&运算把n的最右边的1的位变成0，因为除了1其他2的幂都是只有1位是1，所以如果这个1变成了0，结果就会变成0，也就是&运算后等于0就是2的幂
return n >= 1 && (n & (n - 1)) == 0;
}
}
提交代码后，执行用时1ms，时间击败100.00%的用户，内存消耗35.4MB，空间击败82.22%的用户。
方法3
有没有想过还有更骚的方法？
俗话说，武功再高，也怕菜刀。这句话用在算法上就是，算法再牛，也怕暴力破解。
我们拍一拍自己的脑袋，去想一想，摸一摸，在整数范围内，2的幂一共多少个？
题目已经说了，整数的范围是：-2^31 <= n <= 2^31 - 1。
所以我们拍拍脑袋就可以摊牌了，答案就是从2的0次幂到2的30次幂。
写个java程序把所有的答案列举出来：
public class Main {
public static void main(String[] args) {
showAllTwoPower();
}
private static void showAllTwoPower() {
int num = 1;
for (int i = 0; i <= 30; ++i) {
System.out.println("2的" + i + "次幂：" + num);
num *= 2;
}
}
}
打印结果：
所以解答代码为：
class Solution {
public boolean isPowerOfTwo(int n) {
// 暴力破解所有
switch (n) {
case 1:
case 2:
case 4:
case 8:
case 16:
case 32:
case 64:
case 128:
case 256:
case 512:
case 1024:
case 2048:
case 4096:
case 8192:
case 16384:
case 32768:
case 65536:
case 131072:
case 262144:
case 524288:
case 1048576:
case 2097152:
case 4194304:
case 8388608:
case 16777216:
case 33554432:
case 67108864:
case 134217728:
case 268435456:
case 536870912:
case 1073741824:
return true;
}
return false;
}
}
提交代码后，执行用时1ms，时间击败100.00%的用户，内存消耗35.1MB，空间击败99.41%的用户。
骚不骚？
总结解题
掌握位运算，想多骚有多骚；三十六计，暴力破解为上计。
