image.png

這個題的思路是比較簡單的
大家先想一下，一個十進制整數(shù)是如何轉(zhuǎn)化為二進制數(shù)的？？？
我們采用的是“除2取余，逆序排列"法。具體做法是：用2整除十進制整數(shù)，可以得到一個商和余數(shù)；再用2去除商，又會得到一個商和余數(shù)，如此進行，直到商為小于1時為止，然后把先得到的余數(shù)作為二進制數(shù)的低位有效位，后得到的余數(shù)作為二進制數(shù)的高位有效位，依次排列起來。

所以這個思路就是：和2%，看是否為1，為1，結(jié)果加1，否則繼續(xù)

但是我們需要思考一下代碼如何優(yōu)化的問題？
如二進制是100000000000000000000，那我們需要的循環(huán)次數(shù)是多少，這個時間復(fù)雜太高，我們需要優(yōu)化
現(xiàn)在給出C的幾個優(yōu)化方法
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相似，都是將最右側(cè)的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實現(xiàn)的

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