題目15：二進制中1 的個數(shù)
請實現(xiàn)一個函數(shù)，輸入一個整數(shù)，輸出該數(shù)二進制表示中1的個數(shù)。
舉例說明
例如，把9表示成二進制是1001，有2位是1。因此如果輸入9，則該函數(shù)輸出2。
思路
一. 利用Integer類的bitCount()
代碼實現(xiàn)
public class _15 {
public static int numberOfOne(int n) {
return Integer.bitCount(n);
}
public static void main(String[] args) {
System.out.println("數(shù)字 9的二進制表示中的1的個數(shù):"+numberOfOne(9));//2
}
}
輸出：
數(shù)字 9的二進制表示中的1的個數(shù):2
二. 常規(guī)循環(huán)
時間復(fù)雜度
因為是統(tǒng)計1的個數(shù)，那么用輸入整數(shù)的每一位與1的位與運算就可以簡單的實現(xiàn)
代碼實現(xiàn)
public class _15 {
public static int numberOfOne(int n) {
int result = 0;// 記錄數(shù)字中1的位數(shù)
for (int i = 0; i < 32; i++) {//int占32bit
result += (n & 1);
n >>>= 1;
}
return result;
}
public static void main(String[] args) {
System.out.println("數(shù)字 9的二進制表示中的1的個數(shù):"+numberOfOne(9));//2
}
}
輸出：
數(shù)字 9的二進制表示中的1的個數(shù):2
三. n&(n-1)
時間復(fù)雜度，其中 M 表示 1 的個數(shù)。
一個結(jié)論
結(jié)論：一個數(shù)與該數(shù)減一的結(jié)果進行與運算n&(n-1)，會把該數(shù)右邊（低位）第一個1變?yōu)?，而該位左邊保持不變（高位）
例子：比如1100（對應(yīng)十進制是12），減去1之后的結(jié)果是1011（也就是十進制的11），兩個數(shù)進行與運算之后，我們發(fā)現(xiàn)最后的結(jié)果是1000（對應(yīng)十進制的8，當(dāng)然這個8與后面沒有關(guān)系，可以略過）。這樣我們每進行一次的與運算就消去一個1，這樣消到最后肯定是0了，所以我們可以在代碼中以這個為循環(huán)的終止條件。
代碼實現(xiàn)
public class _15 {
public static int numberOfOne(int n) {
int result = 0;// 記錄數(shù)字中1的位數(shù)
while (n != 0) {// 數(shù)字的二進制表示中有多少個1就進行多少次操作
result++;
// 從最右邊的1開始，每一次操作都使n的最右的一個1變成了0，
// 即使是符號位也會進行操作
n = (n - 1) & n;
}
return result;
}
public static void main(String[] args) {
System.out.println("數(shù)字 9的二進制表示中的1的個數(shù):"+numberOfOne(9));//2
}
}
輸出：
數(shù)字 9的二進制表示中的1的個數(shù):2
相關(guān)題目：
2的冪
用一條語句判斷一個整數(shù)是不是2的整數(shù)次方。
一個整數(shù)如果是2的整數(shù)次方，那么它的二進制表示中有且只有一位是1，其他位均為0
把該整數(shù)減去1后再和它自己做與運算，那么整數(shù)中唯一的1就變成0
從m變成n,改變的bit數(shù)目
輸入兩個整數(shù)m和n，計算需要改變m的二進制表示中的多少位才能得到n。
如10的二進制表示為1010,13的二進制表示為1101，所以兩個數(shù)中不同的位均需要改變，統(tǒng)計兩數(shù)中不同的位的個數(shù)即可；
分兩步解決：
- 求這兩個數(shù)的異或
- 統(tǒng)計結(jié)果中1的位數(shù)
