题解 | #二进制中1的个数#

问题描述：输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示。

示例1

输入：10

返回：2

本题直接的办法是将整数转换为二进制数并存入数组中，然后遍历这个二进制数组从而得到二进制中1的个数。但是遍历的次数为32次。当然我们是否可以将这一过程巧妙化，设置一个计数变量c，用于记录1的个数，一个整数的二进制数中，从右往左计数，如果存在1，则计数，并将二进制中的1去掉，举例来说如输入整数10，其二进制数为1010，从右往左计数，则c++，我们希望更新之后的二进制变为1000，直到二进制数变为0000终止计数。而在二进制中实现这一过程的方法为，其中一个二进制的数减1，就是将这个二进制最右边的那个1变成0，然后它后边的所有位置都变成1，如二进制(1010-1)=1001，而后并操作机会将就会将有0的位置都变成0，即1010&1001=1000，此时n去掉了从右侧开始的1，接着继续做这样的操作，直到n变为0000，从而达到目的。

给一个整数10，其二进制数为1010。每次做一次，n的二进制表示中的最后一位的1都会变成0，如表中所示。

	$n$	$n-1$		$c$
第1次	1010	1001	1000	1
第2次	1000	0111	0000	2
第3次	0000	循环结束

C++核心代码

class Solution {
public:
     int  NumberOf1(int n) {
         int c =0 ;//设置计数变量
         while(n)
         {
             c++;
             n &= (n -1) ;//一个二进制的数减1，就是将这个二进制最右边的那个1变成0，然后它后边的所有位置都变成1
             //并操作就会将有0的位置都变成0，然后再赋值给n，这时n就去掉了一个1
         }
         return c;
         
     }
};

• 时间复杂度:  计算时间为二进制数中1的个数k，即为$O(k)$
• 空间复杂度：借助了一个计数变量，显然空间复杂度为$O(1)$

上面说到本题可以采用直接对二进制数中1的个数计数，设置计数变量count，题目中提到整数为32位二进制，因此共循环遍历32次，每次右移i位数，而后与1相并，因为1的二进制数中前31位均为0，因此如果右移后的整数二进制最后一位为1，则直接计数，否则不计数。

给一个整数10，其二进制数为1010。(此处应为32位二进制，由于前面均为0，因此省去，但是循环仍未32次)

循环次数	$i$	$n<<i$		$count$
1	0	1010	0	0
2	1	101	1	1
3	2	10	0	1
4	3	1	1	2
5	4	0	0	2
...
31	30	0	0	2
32	31	0	0	2

# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1(self, n):
        # write code here
        count = 0;
        for i in range(0,32):
            count+=(n>>i & 1)#每次右移i位数，而后与1相并，因为1的二进制数中前31位均为0，因此如果右移后的整数二进制最后一位为1，则直接计数，否则不计数
            
        return count

• 时间复杂度:每次的循环次数为32次，因此时间复杂度为$O(32)$
• 空间复杂度:借助了一个计数变量，因此空间复杂度为$O(1)$