本來定好每個星期寫一遍算法的博客的，可是因為最近趕項目，博客停止更新一段時間了，現(xiàn)在抽空繼續(xù)更新。本來心情挺好的，一看手機，欠費兩百多，真是日了狗了，百度云沒有設(shè)置只能 wifi 下下載和上傳，用了我的流量來下載，我的內(nèi)心是崩潰的。
一、判斷一個整數(shù)是否是2的乘方
1.題目：實現(xiàn)一個方法，判斷一個正整數(shù)是否是2的乘方（比如 16 是 2 的 4 次方，返回 True；18 不是 2 的乘方，返回 False ）。要求性能盡可能高。
解法一：
創(chuàng)建一個變量 Temp ，初始值是 1 。然后進入一個循環(huán)，循環(huán)中每次讓Temp和目標整數(shù)比較，如果相等，則說明目標整數(shù)是 2 的乘方；如果不相等，則讓 Temp 增大乘 2 ，繼續(xù)循環(huán)比較。當 Temp 大于目標整數(shù)時（所以循環(huán)的判斷條件是小于等于），說明目標整數(shù)不是 2 的乘方。
/**
* 判斷整數(shù)（number）是否是2的乘方
*
* @param number
* @return
*/
public static boolean isPower2_ONE(int number) {
int temp = 1;
while (temp <= number) {
if (temp == number) {
return true;
}
temp = temp * 2;
}
return false;
}
優(yōu)化：
先了解一個知識點：<<(左移)乘二,>>(右移)除二
具體的介紹：
java的左移和右移不是循環(huán)移動，遵循下面的規(guī)則：
1.右移
右移運算用來將一個數(shù)的二進制位序列右移若干位。例如 x>>=2 ,使 x 的各二進制位右移兩位，移到右端的低位被舍棄，最高位則移入原來高位的值。例如：x=00110111,則 x>>2 為 00001101 ; y=11010011 ,則 y>>2 為11110100
2.左移
左移運算用來將一個數(shù)的二進制位序列左移若干位。例如 x<<=2 ,使 x 的各二進制位左移兩位，右邊補 0 ，若x=00001111，則x<<2為00111100.最高位左移后溢出，舍棄不起作用。
右移運算相當于對這個數(shù)字除2取商，左移運算相當于對這個數(shù)字乘2，而且使用左移右移實現(xiàn)乘法除法比使用乘法除法運算速度要快。
注意：以上等效是在不溢出的情況下進行。對于負數(shù)運算的左移是必然會溢出的
當然，如果要實現(xiàn)對負數(shù)的操作，由于計算機在處理負數(shù)的時候是對補碼進行操作，所以除2其實是對補碼的操作，因此對負數(shù)的操作需要對補碼進行處理。
注意：補碼運算的時候，最與最高位符號位是要保持不變的。另外，如果左移右移大于數(shù)據(jù)類型長度時候，會先取模。比如 int i ,左移 33 ,會變?yōu)樽笠?1 ,也就是 33%32
因此我們可以把上面循環(huán)中的乘 2 ，換成左移一位，因為左移運算符會比乘法的效率快很多。
/**
* 判斷整數(shù)（number）是否是2的乘方（把乘2換成左移一位）
*
* @param number
* @return
*/
public static boolean isPower2_TWO(int number) {
int temp = 1;
while (temp <= number) {
if (temp == number) {
return true;
}
temp = temp << 1;
}
return false;
}
雖然換成左移運算法效率會變快，可是時間復(fù)雜度還是沒有變化的，也就是說本質(zhì)還是沒有改變。
解法二：
觀察下面的圖，我們可以發(fā)現(xiàn)什么規(guī)律呢？
通過觀察我們可以發(fā)現(xiàn)：
(1) 凡是2的乘方的正整數(shù)，其二進制數(shù)必然是以 1 為首位，其它位都是 0
(2) 如果給它減 1 ，（在位數(shù)相同的情況下）就會變成首位是 0 ，其它位全部是 1 的結(jié)果
(3) 0 和 1 的按位與運算結(jié)果是 0 ，因此 2 的乘方和他本身減1相與，即 N & N-1，結(jié)果必然是 0；也就是說用“位與”運算，得到的結(jié)果是0,就說明這個正整數(shù)是2的乘方
所以，2 的乘方都符合一個規(guī)律，即 N&N-1 等于 0，所以直接用這個規(guī)律判斷即可，但是，這個結(jié)論就一定正確嗎？這只是我們通過觀察部分數(shù)據(jù)得出的結(jié)果，況且我們的數(shù)據(jù)量非常的少，怎樣才能保證這個結(jié)論是正確的呢？我們可以通過反證法來證明：
假設(shè)真的存在一個正整數(shù) N，N 不是 2 的冪，但是 N 符合 N&N-1 =0。
由 N 不是 2 的冪可以推斷出，N 的二進制形式并不是除了最高位是1以外，其余為全是 0 。
既然其余位不全是 0 ，那么 N-1 的結(jié)果的最高位一定不會改變，仍然是1。
既然 N-1 的最高位是 1 ，N的最高位也是 1 ，那么 N&N-1！=0，和假設(shè)矛盾。
由此證明，符合 N&N-1 =0 的正整數(shù)必然是 2 的冪。
最后我們用代碼來實現(xiàn)：
/**
* 判斷整數(shù)（number）是否是2的乘方（位與運算）
*
* @param number
* @return
*/
public static boolean isPower2_THREE(int number) {
return (number & number - 1) == 0;
}
二、求出一個正整數(shù)轉(zhuǎn)換成二進制后的數(shù)字“1”的個數(shù)
題目：求出一個正整數(shù)轉(zhuǎn)換成二進制后的數(shù)字“1”的個數(shù)
如：
int 型數(shù)值為 80
轉(zhuǎn)化成二進制形式：80 = 00000000 00000000 00000000 01010000
因此 1 的個數(shù)為 2
解法一：
由上面的位運算判斷 2 的乘方可以知道，n&(n-1) 可以把整數(shù)二進制的最右邊的數(shù)由 1 變?yōu)?0 ，利用這個我們就可以解決這個問題了。
具體實現(xiàn)的代碼如下：
/**
* 計算一個int型數(shù)值中bit-1的個數(shù)
*
* @param n
* @return
*/
public static int bitCount1(int n) {
int count = 0;
while (n != 0) {
n = n & (n - 1);
count++;
}
return count;
}
解法二：
我們也可以通過移位來解決這題,因為整數(shù)的二進制與 1 進行 & 運算的時候，當最末位也就是最右邊的一位為 1 的時候，結(jié)果就是 1 ，判斷完最后一位，然后把整數(shù)的二進制右移一位，再判斷，直到整數(shù)等于 0 結(jié)束循環(huán)
/**
* 計算一個int型數(shù)值中bit-1的個數(shù)
*
* @param n
* @return
*/
public static int bitCount2(int n) {
int count = 0;
while (n > 0) {
if ((n & 1) == 1) {// 如果最右邊的值是1
count++;
}
n >>= 1; // 向右一位
}
return count;
}
可是這種做法不是太好，因為 Java 中 int 占 4 個字節(jié)，一共 32 位，那么就是說，要循環(huán) 32 次才能結(jié)束
解法三：
其實這個題目在 Java ，Integer 類中 bitCount 方法的已經(jīng)解決了的，我們可以看下大神們是如何巧妙的解決的。
一開始沒想明白怎么推出來的，最后上網(wǎng)查了一下，
歡迎轉(zhuǎn)載，轉(zhuǎn)載請標明來源：
CSDN主頁：http://blog.csdn.net/two_water
簡書主頁：http://www.itdecent.cn/users/8ec863a03f4f/latest_articles
