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
