输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

题目描述

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

分析：首先需要判断n是不是负数，当n为负数的时候，直接用while循环判断会导致死循环，因为负数向左移位的话最高位补1 。

针对这种情况，要不就是对正数和负数的操作应该分开处理，要不就是找到一个对正数和负数都可以处理的方法。

如果是第二种方法可以把int型转成二进制的string类型，再统计string类型中1的个数。这样正数和负数就都可以处理了。

统计二进制1的个数第一版：

public class Solution {

    public static void main(String[] args){
        long startTime=System.nanoTime();   //获取开始时间
        int num = NumberOf1(7);
        long endTime=System.nanoTime(); //获取结束时间
        System.out.println(num);
        System.out.println("程序运行时间： "+(endTime-startTime)+"ns");
    }
    public static  int NumberOf1(int n) {
        //return Integer.bitCount(n);
        int count =0;
        String str = Integer.toBinaryString(n);
        char[] chararr = str.toCharArray();
        for(int i=0;i<chararr.length;i++){
        if(chararr[i]=='1'){
              count++;
           }
        }
        return count;
    }
}

运行结果：

但是这种方法时间复杂度比较高， 涉及到了整数转字符串的操作。那么有什么什么方法可以降低算法的时间复杂度？

刚才也说了，负数的情况需要特殊考虑，那有什么办法把负数的特殊情况转换一下，变成都是对正数的处理呢？

需要对负数做一点点特殊操作，可以将最高位的符号位1变成0，也就是n & 0x7FFFFFFF，这样就把负数转化成正数了，唯一差别就是最高位由1变成0，因为少了一个1，所以count加1。之后再按照while循环里处理正数的方法来操作就可以啦！

对正数处理的话就是不断除二再根据除二的余数做num++的计算。 

统计二进制1的个数第二版：

public class Solution {

    public static void main(String[] args){
        long startTime=System.nanoTime();   //获取开始时间
        int num = NumberOf1(7);
        long endTime=System.nanoTime(); //获取结束时间
        System.out.println(num);
        System.out.println("程序运行时间： "+(endTime-startTime)+"ns");
    }
    public static  int NumberOf1(int n) {
        int count = 0;
        if(n < 0) {
            n = n & 0x7FFFFFFF;
            count ++;
        }
        while(n!=0){
            if(n%2!=0){
                count++;
            }
            n/=2;
        }
        return count;
    }
}

从运行结果来看程序运行时间明显缩短，程序的运行效率大幅提升了。 

但这还不是最优的解法，我们在执行while循环的时候，为了遍历n使用了对n进行递归除2的操作，除了使用除2操作，把整数右移一位和把整数除以2在数学上是等价的，那么这两个操作在计算机上的执行效率是一样的吗？

在计算机中，除法的效率比移位运算要低得多，在实际变成中应尽可能的利用以为运算代替乘除法。同理，取余操作的效率也是明显低于和1做与运算的，这两个操作都能打到同样的效果，但是与运算的效率更高一些。

那么我们就可以对代码做如下修改了。

统计二进制1的个数第三版：

public class Solution {

    public static void main(String[] args){
        long startTime=System.nanoTime();   //获取开始时间
        int num = NumberOf1(7);
        long endTime=System.nanoTime(); //获取结束时间
        System.out.println(num);
        System.out.println("程序运行时间： "+(endTime-startTime)+"ns");
    }
    public static  int NumberOf1(int n) {
        int count = 0;
        if(n < 0) {
            n = n & 0x7FFFFFFF;
            count ++;
        }
        while(n!=0){
            if((n&1)==1){
                count++;
            }
            n=n>>1;
        }
        return count;
    }
}

 

可以看到程序的运行时间又缩短了一些，因为测试的数字不是很大，所以缩短的时间的效果不是很明显。

但是上述代码仍然不是最优的，那我们还可以从哪个地方去做优化呢？

把一个整数减去1在与它本身做与运算，就会把该整数最右边一个1变成0。那么一个整数的二进制有多少个1，就可以进行多少次这样的操作就可以了。

举个例子：一个二进制数1100，从右边数起第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成了1，而前面的1保持不变，因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000。

用这种方法也不用考虑正负数的问题了，运行效率也会很高，代码也缩短了。

统计二进制1的个数第四版：

public class Solution {

    public static void main(String[] args){
        long startTime=System.nanoTime();   //获取开始时间
        int num = NumberOf1(7);
        long endTime=System.nanoTime(); //获取结束时间
        System.out.println(num);
        System.out.println("程序运行时间： "+(endTime-startTime)+"ns");
    }
    public static  int NumberOf1(int n) {
        int count = 0;
        while(n!= 0){
            count++;
            n = n & (n - 1);
        }
        return count;
    }
}

运行结果：

 

可以看到程序执行的时间进一步缩短了。 

除了自己写程序实现之外，Java中还封装了现成的统计整数二进制中1的个数的方法，我们可以直接使用。

统计二进制1的个数第五版：

public class Solution {

    public static void main(String[] args){
        long startTime=System.nanoTime();   //获取开始时间
        int num = NumberOf1(7);
        long endTime=System.nanoTime(); //获取结束时间
        System.out.println(num);
        System.out.println("程序运行时间： "+(endTime-startTime)+"ns");
    }
    public static  int NumberOf1(int n) {
        return Integer.bitCount(n);
    }
}

执行结果： 

可以看到使用内置方式执行的结果并不是最高效的。

一个简单的统计整数二进制中1的个数的算法就可以有好几个，他们有的效率高，有的效率低。在编程中，我们不仅要实现算法的功能，还要考虑到算法的时间复杂度和空间复杂度，考虑的东西要全面一些，每一道问题都争取写出执行效率最优的算法。