LeetCode 筆記 - 191. Number of 1 Bits

⚠️ 舊文提醒：本文發佈於約 4 年前，部分內容或指令可能已過時，請斟酌參考。

給定一個數字，請計算出在 Binary 中 1 的數量

解題思維

這個計算其實就是漢明距離

簡單一點可以實作 Binary 轉換演算法
在過程中計算 1 的數量即可

而目前已知最快速演算法
會持續地將 x 與 x - 1 做 and 所得到的最低位永遠為 0，藉此來快速移除 1

例如

Expression	Value
X	0 1 0 0 0 1 0 0 0 1 0 0 0 0
X-1	0 1 0 0 0 1 0 0 0 0 1 1 1 1
X & (X-1)	0 1 0 0 0 1 0 0 0 0 0 0 0 0

程式碼請看第二種範例

完成 😎

程式碼

class Solution:
    def hammingWeight(self, num: int) -> int:

        result = 0
        check = 1
        while check <= num:
            if num & check != 0:
                result += 1
            check = check << 1
            
        return result

高效演算法

class Solution:
    def hammingWeight(self, num: int) -> int:        
        weight = 0

        while num:
            weight += 1
            num &= num - 1

        return weight

解題思維

程式碼

也許你也會想看看