劍指offer——11二進制中1的個數(Python)

【題目】輸入一個整數，輸出該數二進制表示中1的個數。其中負數用補碼表示。

【思路】将輸入先轉換為二進制，然後将其轉化為字元串，逐位與 1比較，若等于1 ，結果加1。

【代碼實作】

class Solution:
    def NumberOf1(self, n):
        # write code here
        #補碼：正數不變，負數是它正數的反碼+1
        #0x表示16進制，F表示4個1
        n = 0xFFFFFFFF & n #取一個數的補碼的後32位
        s = str(bin(n))
        count = 0
        for c in s:
            if c == "1":
                count += 1
        return count
           

【方法二】我們可以用1從n的右邊進行與操作，不為0的話該位就是1，然後不斷移位依次比較:

class Solution:
    def NumberOf1(self, n):
        count = 0
        for i in range(32):
            flag = 1 << i
            if n & flag != 0:
                count += 1
        return count
        #同理也可讓n右移與1比較        
        count = 0
        for i in range(32):
            if n>>i & 1 != 0:
                count += 1
            
        return count
           

【方法三】把一個整數減去1，再和原來的整數做與運算，會把該二進制整數最右邊的1變成0；根據這個原理可得，一個整數有多少個1，就可以執行多少次與運算，則：

count = 0
        while n:
            n = 0xFFFFFFFF & n #可能有負數，取補碼的後32位
            n = n&(n-1)
            count += 1
        return count