本文轉載自【微信公眾號：五角錢的程式設計師，ID:xianglin965】經微信公眾號授權轉載，如需轉載與原文作者聯繫
文章目錄
15. 二進位中 1 的個數題目連結題目描述思路一. 利用Integer類的bitCount()二. 常規循環三. n&(n-1)
15. 二進位中 1 的個數
題目連結
NowCoder
題目描述
任意給定一個32位無符號整數n，求n的二進位表示中1的個數，比如n = 5（0101）時，返回2，n = 15（1111）時，返回4
這也是一道比較經典的題目了，相信不少人面試的時候可能遇到過這道題吧，下面介紹了幾種方法來實現這道題，相信很多人可能見過下面的算法，但我相信很少有人見到本文中所有的算法。如果您上頭上有更好的算法，或者本文沒有提到的算法，請不要吝惜您的代碼，分享的時候，也是學習和交流的時候。
思路
一. 利用Integer類的bitCount()
代碼實現
package 二進位一的個數;/*
作者 :XiangLin
文件 :BitCount1.java
IDE :IntelliJ IDEA
*/
public class BitCount1 {
public static int numberOfOne(int n){
return Integer.bitCount(n);
}
public static void main(String[] args) {
System.out.println("數字 10的二進位表示中的1的個數:"+numberOfOne(10));
}
}
二. 常規循環
時間複雜度O(logN)
因為是統計1的個數，那麼用輸入整數的每一位與1的位與運算就可以簡單的實現
代碼實現
public class BitCount2 {
public static int numberOfOne(int n){
int result = 0;// 記錄數字中1的位數
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("數字 9的二進位表示中的1的個數:"+numberOfOne(9));//2
}
}
是最簡單的方法，有點程序基礎的人都能想得到，那就是移位+計數，很簡單，不多說了，直接上代碼，這種方法的運算次數與輸入n最高位1的位置有關，最多循環32次。
public class BitCount2{
public static int numberOfOne(int n){
int result = 0;
while (n > 0){
if ((n & 1) == 1){
++ result;
}
n >>>= 1;
}
return result;
}
public static void main(String[] args) {
System.out.println("數字 11的二進位表示中的1的個數:"+numberOfOne(11));//2
}
}
三. n&(n-1)
時間複雜度，其中 M 表示 1 的個數。
一個結論
結論：一個數與該數減一的結果進行與運算n&(n-1)，會把該數右邊（低位）第一個1變為0，而該位左邊保持不變（高位）
例子：比如1100（對應十進位是12），減去1之後的結果是1011（也就是十進位的11），兩個數進行與運算之後，我們發現最後的結果是1000（對應十進位的8，當然這個8與後面沒有關係，可以略過）。這樣我們每進行一次的與運算就消去一個1，這樣消到最後肯定是0了，所以我們可以在代碼中以這個為循環的終止條件。
package 二進位一的個數;
/*
作者 :XiangLin
文件 :BitCount3.java
IDE :IntelliJ IDEA
*/
public class BitCount3 {
public static int numberOfOne(int n){
int result = 0;// 記錄數字中1的位數
while (n != 0){// 數字的二進位表示中有多少個1就進行多少次操作
result ++;
n = n&(n-1);
}
return result;
}
public static void main(String[] args) {
System.out.println("數字 9的二進位表示中的1的個數:"+numberOfOne(9));
}
}