二进制中有多少个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中如何实现，暂时没有想到。