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

￡神魔★判官ぃ 2022-05-15 05:56 136阅读 0赞

题目描述

分析：`首先需要判断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;
        }
    }

运行结果：

![70][]

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

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

`需要对负数做一点点特殊操作，可以将最高位的符号位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;
        }
    }

![70 1][]

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

但这还不是最优的解法，我们在执行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;
        }
    }

![70 2][]

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

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

把一个整数减去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;
        }
    }

运行结果：

![70 3][]

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

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

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

执行结果：![70 4][]

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

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

[70]: /images/20220515/a283630ba94f4ca9bc00fb1d3d7446d2.png
[70 1]: /images/20220515/32a06b54804a4d0e997fecbfb212df48.png
[70 2]: /images/20220515/f46858614f124f0fa057774c1d14b010.png
[70 3]: /images/20220515/632ce6096eba43739c53dd63580f8972.png
[70 4]: /images/20220515/629ec776a5ec4a80aa255517a37a227e.png