二進制中有多少個1

計算一個十進制數轉為二進制後有多少個1（或者0）

樣例：

給定32（100000）傳回1

給定5（101）傳回2

分析

方法一：普通法

public int countOnes1(int num){
        int count = 0;
        while(num!=0){
            if(num%2==1)
                count++;
            num=num/2;
        }
        return count;
    }
           

方法二:位移法（但是當num為負數時會報錯）

public int countOnes2(int num){
     int count=0;
     while(num!=0){
        if(num&1==1)count++ ;
        num>>1;
     }
     return count;
 }
           

方法三：位移法改進

思路：将整數n與1進行與運算，當整數n最低位是1時，則結果非零，否則結果為0。

然後将1左移一位，繼續與n進行與運算，當次低位是1時，結果非零，否則結果為0。

循環以上操作，記錄非零的次數即可。

public int countOnes3(int num){
    	int flag=1;
        int count=0;
        while(flag<=num){
        	if((num&flag)!=0)count++;
            flag=flag<<1;
        }
        return count;
    }
           

方法四：

思路： 這種方法速度比較快，其運算的次數與n的大小無關，隻與n中1的個數有關。如果n的二進制中有k個1，這個方法隻要循環k次。

1.對一個整數n，比如10，它的二進制是1010。

2.将10減一變為9，9的二進制是1001.

3.比較10和9的二進制數，對10減一操作就等于将10的二進制的最低位上的1以及後面的位取反，前面的數不變。

總結：把一個整數減去1，再和原整數做與運算，會把該整數最右邊1一個1變成0。那麼一個整數的二進制表示中有多少個1，就可以進行多少次這樣的操作。進而可以減少比較的次數。

public int countOnes(int num){
    	int count = 0;
        while(num!=0){
        	count++;
            n=n%(n-1);
        }
        return count;
    }
           

相應的求解0就是n=n|(n+1)，但是在java中如何實作，暫時沒有想到。