【轉】判斷一個整數轉換成二進制後1的個數

判斷一個整數轉換成二進制後1的個數，大緻有三種方法，分别是左移位、右移位和與運算。

第一種方法：右移位

        右移位的基本思路是，先将整數轉換成正整數，再将該數與1進行與運算。若不将整數做取絕對值處理，當輸入的數是負數時，每向右移動一位，高位會自動補1，就會導緻死循環

1. int ChargeOnesCountInNum1(int iNum)  
2. {  
3.     int iCount=0;  
4.     iNum = abs(iNum);//注意添加上了絕對值  
5.     while(iNum){  
6.         if (iNum & 1){  
7.             ++iCount;  
8.         }  
9.         iNum = iNum >> 1;  
10.     }  
11.     return iCount;  
12. }  

第二種方法：左移位

        左移位的基本思路和右移位相同。

1. int ChargeOnesCountInNum2(int iNum)  
4.     unsigned int iFlag = 1;  
6. </span>   while(iFlag){  
7.         if (iNum & iFlag){  
10.         iFlag = iFlag << 1;  

第三種方法：與運算

        将一個整數減去1之後，其對應的二進制中最右邊的一個1會變為0，若其後存在0，則其之後的所有0都會變為1。基于此，設一個整數為n，則 n & (n-1)之後，會消掉n對應的二進制的最右邊的1。是以，将一個數中所有1消掉所用的次數，即為該整數對應的二進制中1的個數。

1. int ChargeOnesCountInNum3(int iNum)  
6.         ++iCount;  
7.         iNum = iNum & (iNum-1);  

        左移位或者是右移位，while循環執行的次數取決于計算機的位數，32位的計算機就執行32次，而64位則要執行64次。而與運算的方法執行的次數，隻與該數中1的個數有關。是以與運算方法，是三種方法中最好的一個。

相關的變形問題

• 用一條語句判斷一個整數是不是2的整數次方。參考答案：if ( !(iN & (iN-1)) ){}
• 輸入兩個整數m和n，計算m和n對應的二進制中有多少個不同的位。參考思路：先對m和n進行異或，然後計算異或後的二進制結果中1的個數。