[TOC]
# 题目
**实现一个方法，判断一个正整数是否是2的乘方（比如16是2的4次方，返回True；18不是2的乘方，返回False）。要求性能尽可能高**
# 解法
## 解法一
创建一个中间变量Temp，初始值是1。然后进入一个循环，循环中每次让Temp和目标整数比较，如果相等，则说明目标整数是2的乘方；如果不相等，则让Temp增大一倍，继续循环比较。当Temp大于目标整数时，说明目标整数不是2的乘方。
如果目标整数的大小是N，则此方法的时间复杂度是O（LogN）。
~~~
public static boolean isPowerOf2 (int number) {
int temp = 1;
while (temp <= number) {
if (temp == number) {
return true;
}
temp = temp * 2;
}
return false;
}
~~~
那么这样写是可以,但是思考下如何提高性能?
## 解法二
把之前的乘以2操作改成向左移位,移位的性能比乘法高的多
~~~
public static boolean isPowerOf2 (int number) {
int temp = 1;
while (temp <= number) {
if (temp == number) {
return true;
}
temp = temp << 1;
}
return false;
}
~~~
这样确实有优化,但是目前算法的事件复杂度仍然是O(logN),本质上没有变,如何才能在性能上有质的飞越?
### 关于移位
移位实现的乘除法比直接乘除的效率高很多。
用移位实现乘除法运算
~~~
a=a*4;
b=b/4;
可以改为：
a=a<<2;
b=b>>2;
~~~
说明：
除2 = 右移1位 乘2 = 左移1位
除4 = 右移2位 乘4 = 左移2位
除8 = 右移3位 乘8 = 左移3位
... ...
通常如果需要乘以或除以2的n次方，都可以用移位的方法代替。
大部分的C编译器,用移位的方法得到代码比调用乘除法子程序生成的代码效率高。
实际上，只要是乘以或除以一个整数，均可以用移位的方法得到结果，如：
~~~
a=a*9
分析a*9可以拆分成a*(8+1)即a*8+a*1, 因此可以改为： a=(a<<3)+a
a=a*7
分析a*7可以拆分成a*(8-1)即a*8-a*1, 因此可以改为： a=(a<<3)-a
~~~
## 解法三
这题目有O(1)的解法
思路
把这个2的乘法结果转换成2进制数,会有什么共同点?
十进制的2转成二进制是10B,4转成二进制是100B,8转成二进制是1000B...
如果一个整数是2的乘方,那么它转换成2进制的时候,只有一位是1
那么如果把2的乘方都减去一呢?转换成2进制数,会有什么样的特点?
2乘方的二进制形式原本都只有最高位是1,如果减去1,那么整个数减少一位,其他位由0变为1
这时候如果我们用2的乘方本身和他减一的结果进行按位与运算,也就是N & N-1,会是什么结果?
0和1的按位与运算结果是0,所以凡是2的乘方和它本身减一相与,即`N & N-1`,结果必然是0!
那么我们的解法是不是很简单了?
只需要计算N & N-1
**解法**
非常有趣也非常简单的解法。因为2的乘方都符合一个规律，即 N&N-1 等于 0，所以直接用这个规律判断即可。该算法时间复杂度是O（1）
~~~
public static boolean isPowerOf2 (Interger number) {
return (number & number-1) == 0;
}
~~~
# 扩展
**实现一个方法，求出一个正整数转换成二进制后的数字“1”的个数。要求性能尽可能高**
这题仍然可以用位运算的思路
