第 15 題：二進(jìn)制中 的個(gè)數(shù)

傳送門：二進(jìn)制中 的個(gè)數(shù)，?？途W(wǎng) online judge 地址。

輸入一個(gè) 32 位整數(shù)，輸出該數(shù)二進(jìn)制表示中1的個(gè)數(shù)。

注意：

• 負(fù)數(shù)在計(jì)算機(jī)中用其絕對(duì)值的補(bǔ)碼來表示。

樣例1：

輸入：9
輸出：2
解釋：9 的二進(jìn)制表示是 1001，一共有 2 個(gè) 1 。

樣例2：

輸入：-2
輸出：31
解釋：-2 在計(jì)算機(jī)里會(huì)被表示成 11111111111111111111111111111110，一共有 31 個(gè) 1 。

知識(shí)點(diǎn)：1、什么是補(bǔ)碼？補(bǔ)碼就是一個(gè)數(shù)與另一個(gè)數(shù)相加，是一個(gè)進(jìn)制表示下很整的數(shù)；

2、正數(shù)的補(bǔ)碼就是它自己，負(fù)數(shù)在計(jì)算機(jī)中的表示是它的補(bǔ)碼；

3、數(shù)分為：“有符號(hào)整數(shù)”與“無符號(hào)整數(shù)”。

記?。?、n & (n - 1) 把最低位的 變成 。

2、Python 中的二進(jìn)制有陷阱，參考資料：https://www.cnblogs.com/klchang/p/8017627.html。

筆記：

二進(jìn)制中 1 的個(gè)數(shù)-1

二進(jìn)制中 1 的個(gè)數(shù)-2

分析：位運(yùn)算的問題，看答案做出來的，記住 n & (n-1) 能夠消掉最低位的 即可。

Python 代碼1：一位一位算就可以了，注意，做 次就可以了。

class Solution(object):
    def NumberOf1(self, n):
        """
        :type n: int
        :rtype: int
        """
        ans = 0
        for i in range(32):
            if n & 1:
                ans += 1
            n = n >> 1

        return ans

Python 代碼2：Python 中的數(shù)是長(zhǎng)整型，因此一開始做的時(shí)候，要把高于 位的全部砍掉

class Solution(object):
    def NumberOf1(self, n):
        """
        :type n: int
        :rtype: int
        """
        # print((-1 & (2**31-1)) >> 1)
        # print((-3) >> 1)
        n = n & (2 ** 32 - 1)
        # print(n)
        count = 0
        while n != 0:
            if n & 1 == 1:
                count += 1
            n = n >> 1
            # print(n)
        return count

Python 代碼：以下寫法等價(jià)

class Solution(object):
    def NumberOf1(self,n):
        """
        :type n: int
        :rtype: int
        """
        counter  = 0
        
        # Python 中的 32 位整數(shù)沒有溢出這回事，所以要強(qiáng)行變成 32 位
        # 這一步相當(dāng)于把這個(gè)數(shù)變成無符號(hào)整數(shù)，為了通過 judge 才這么做的
        
        n = n & 0xFFFFFFFF
        
        while n:
            n = n &(n-1)
            counter +=1
        return counter

C++ 寫法：轉(zhuǎn)成無符號(hào)數(shù)。

二進(jìn)制中 1 的個(gè)數(shù)-3

二進(jìn)制中 1 的個(gè)數(shù)-4

• Java 寫法

思路1：

• 熟悉位運(yùn)算是關(guān)鍵。
• 負(fù)數(shù)左移的時(shí)候，最高位補(bǔ) 1，因此，為了避免死循環(huán)，先要把最高位變成 0。

二進(jìn)制中 1 的個(gè)數(shù)-5

二進(jìn)制中 1 的個(gè)數(shù)-6

Java 代碼：

public class Solution {
    public int NumberOf1(int n) {
        int count = 0;
        // 負(fù)數(shù)右移的時(shí)候，最高位補(bǔ) 1，因此，為了避免死循環(huán)，先要把最高位變成 0
        // 負(fù)數(shù)右移的時(shí)候，最高位補(bǔ) 1，因此，為了避免死循環(huán)，先要把最高位變成 0
        // 負(fù)數(shù)右移的時(shí)候，最高位補(bǔ) 1，因此，為了避免死循環(huán)，先要把最高位變成 0

        // 為負(fù)數(shù)的時(shí)候，將最高位的 1 變成 0
        // 即由負(fù)數(shù)變成正數(shù)，然后再計(jì)算 1 的個(gè)數(shù)
        if (n < 0) {
            n = n & Integer.MAX_VALUE;
            count++;
        }

        // 當(dāng) n 是正數(shù)的時(shí)候，計(jì)算 1 的個(gè)數(shù)
        while (n != 0) {
            count += n & 1;
            n = n >> 1;
        }
        return count;
    }
}

思路2：

• 可以使用 1001 作為測(cè)試用例來理解，a&(a-1) 的結(jié)果會(huì)將 a 最右邊的 1 變?yōu)?0 ，直到 a = 0，還可以先將 a&1 != 0,然后右移 1 位，但不能計(jì)算負(fù)數(shù)的值。

二進(jìn)制中 1 的個(gè)數(shù)-7

二進(jìn)制中 1 的個(gè)數(shù)-8

二進(jìn)制中 1 的個(gè)數(shù)-9

Java 代碼：

public class Solution2 {
    public int NumberOf1(int n) {
        int count = 0;
        while (n != 0) {
            count++;
            n = (n - 1) & n;
        }
        return count;
    }
}