[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”的個數。要求性能盡可能高**
這題仍然可以用位運算的思路
