输入一个整数，输出该二进制表示中1的个数

image.png

这个题的思路是比较简单的
大家先想一下，一个十进制整数是如何转化为二进制数的？？？
我们采用的是“除2取余，逆序排列"法。具体做法是：用2整除十进制整数，可以得到一个商和余数；再用2去除商，又会得到一个商和余数，如此进行，直到商为小于1时为止，然后把先得到的余数作为二进制数的低位有效位，后得到的余数作为二进制数的高位有效位，依次排列起来。

所以这个思路就是：和2%，看是否为1，为1，结果加1，否则继续

但是我们需要思考一下代码如何优化的问题？
如二进制是100000000000000000000，那我们需要的循环次数是多少，这个时间复杂太高，我们需要优化
现在给出C的几个优化方法
1、

int NumberOf1(int n)
{
    int res=0;
    while(n!=0)
    {
    n&=(n-1);//我将这个方法称为抹0法，将最右边的1抹掉，
    res++;
    }
    return res;
}

2、

int NumberOf1(int n)
{
    int res=0;
    while(n!=0)
    {
    n-=n&（~n+1)//这对与方法1相似，都是将最右侧的1抹掉
    res++;
    }
    return res;
}

3、来个效率特别高的

int NumberOf1(int n)
{
     n=(n& 0x55555555)+((n>>1)&0x55555555);
     n=(n& 0x33333333)+((n>>2)&0x33333333);
     n=(n& 0x0f0f0f0f)+((n>>4)&0x0f0f0f0f);
     n=(n& 0x00ff00ff)+((n>>8)&0x00ff00ff);
     n=(n& 0x0000ffff)+((n>>16)&0x0000ffff);
     return n;
}

最后再附上一个拿python实现的

class Solution:
    def NumberOf1(self, n):
        count = 0
        if n >= 0:
            s = bin(n)[2:]
        else:
            s = bin(pow(2,32)+n)[2:]
        for i in s:
            if i=='1':
                count+=1
        return count

这是一些基本知识，了解一下，有助于位运算符的理解

image.png