編寫(xiě)一個(gè)函數(shù)，輸入是一個(gè)無(wú)符號(hào)整數(shù)，返回其二進(jìn)制表達(dá)式中數(shù)字位數(shù)為 ‘1’ 的個(gè)數(shù)（也被稱為漢明重量）。

示例 1：

輸入：00000000000000000000000000001011
輸出：3
解釋?zhuān)狠斎氲亩M(jìn)制串 00000000000000000000000000001011 中，共有三位為 '1'。

示例 2：

輸入：00000000000000000000000010000000
輸出：1
解釋?zhuān)狠斎氲亩M(jìn)制串 00000000000000000000000010000000 中，共有一位為 '1'。

示例 3：

輸入：11111111111111111111111111111101
輸出：31
解釋?zhuān)狠斎氲亩M(jìn)制串 11111111111111111111111111111101 中，共有 31 位為 '1'。

方法一：直接遍歷數(shù)字的 32 位。如果某一位是 1 ，將計(jì)數(shù)器加一。
如何確定當(dāng)前位的數(shù)字是1呢？

• 使用與（&）運(yùn)算： 1&1=1 ，1&0=0
• 1 << 1 ，將1左移一位

num = 00000000000000000000000000001011

1 的二進(jìn)制表示是
0000 0000 0000 0000 0000 0000 0000 0001
mask = 00000000000000000000000000000001

第一次比較： 
兩者最后一位都是1，所以1&1=1，計(jì)數(shù)加一

比較完后，就將1左移一位
0000 0000 0000 0000 0000 0000 0000 0010
mask <<= 1
mask = 00000000000000000000000000000010

第二次比較：
都是1，所以計(jì)數(shù)加一

比較完后，將1左移一位
0000 0000 0000 0000 0000 0000 0000 0100
mask <<= 1
mask = 00000000000000000000000000000100

第三次比較：
num第三位是0，所以不計(jì)數(shù)

……

以此類(lèi)推，重復(fù)此過(guò)程，把num的32位都比較一遍，就能獲得答案

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(1) 。這題中 n 是一個(gè) 32 位數(shù)，常數(shù)級(jí)別，所以運(yùn)行時(shí)間是 O(1) 的。
• 空間復(fù)雜度：O(1)。沒(méi)有使用額外空間。

func hammingWeight(num uint32) int {
    //用1去和32位做與（&）運(yùn)算，如果結(jié)果不是0的話 ，說(shuō)明這個(gè)位置的數(shù)字就是1
    count := 0
    mask := uint32(1)
    for i:=0; i<32;i++ {
        fmt.Println(num & mask)
        if (num & mask) != 0{
            count++
        }
        //每次循環(huán)后，1的位置就向左移動(dòng)一位，就像是一個(gè)指針掃描一遍這32位數(shù)一樣
        mask = mask << 1
    }
    return count    
}

方法二：上面的方法，速度會(huì)稍慢些，因?yàn)槊看伪容^都要比較32位，我們可以反向操作，將num向右移1一位，這樣省了內(nèi)存的同時(shí)，每次循環(huán)，比較的次數(shù)都會(huì)變少，因?yàn)閚um的位數(shù)每次都右移，也就是位數(shù)-1

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(1) 。也是常數(shù)級(jí)時(shí)間復(fù)雜度。
• 空間復(fù)雜度：O(1)。沒(méi)有使用額外空間。

func hammingWeight(num uint32) int {
    count := 0
    //也可以反向操作，將num向右移1一位，這樣就省了些內(nèi)存
    /for num !=0 {
        if num & 1 == 1{//讓num與1進(jìn)行按位與運(yùn)算，取得num最低位判斷是否位1
            count++
        }
        num >>= 1//num右移一位
    }
    return count


}

方法三：將 n 和 n?1 做與運(yùn)算，會(huì)把最后一個(gè) 1 的位變成 0

n         10100
n-1       10011
n&n-1     10000

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(1) 。運(yùn)行時(shí)間與 n 中位為 1 的有關(guān)。在最壞情況下， n 中所有位都是 1 。對(duì)于 32 位整數(shù)，運(yùn)行時(shí)間是 O(1) 的。
• 空間復(fù)雜度：O(1) 。沒(méi)有使用額外空間。

func hammingWeight(num uint32) int {
    //在二進(jìn)制表示中，數(shù)字 n 中最低位的 1 總是對(duì)應(yīng)n?1 中的 0 。
    //因此，將 n 和 n?1 與運(yùn)算總是能把 n 中最低位的 1 變成 0 ，并保持其他位不變。
    sum := 0
    for num != 0 {
        sum++
        num &= (num - 1)
    }
    return sum

}