題目:

Write a function that takes an unsigned integer and returns the number of '1' bits it has

給定32位的unsigned integer,回傳它裡頭有幾個1

我一開始想法很單純,用190.的方式
一個一個位數看是不是1,然後放計數器(反正也才32位XD)

class Solution:
    def hammingWeight(self, n: int) -> int:
        ans=0
        for i in range(32):
            if n&1:
                ans=ans+1
            n=n>>1
        return ans

最後執行時間32ms(faster than 91.95%)

後來我又想,既然只是單純的計數,為何不用count呢(逐漸被討論區感染

class Solution:
    def hammingWeight(self, n: int) -> int:
        return bin(n).count("1")

先將其變為二進位字串,算裡面的"1"就好
最後執行時間31ms(faster than 93.84%)

不過在我寫完逛討論區的時候,看到一個十分巧妙的解法
這邊分享一下,比敝人上面兩個沒營養的解法好多了

class Solution:
    def hammingWeight(self, n: int) -> int:
        ans=0
        while n:
            n=n&(n-1)
            ans=ans+1
        return ans

到n變為0為止,不斷和n-1做&運算,看總共執行了幾次
以1100為例,-1就是1011,兩者行&運算會變成1000
可以看到最尾端的1就這麼輕鬆被消掉了
只要知道消了幾次1,就知道該unsigned integer有幾個1了
最後執行時間31ms(faster than 93.84%)

那我們下題見