LeetCode 筆記 - 191. Number of 1 Bits

Posted on

題目在此 191. Number of 1 Bits

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

解題思維

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

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

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

例如

ExpressionValue
X0 1 0 0 0 1 0 0 0 1 0 0 0 0
X-10 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

程式碼請看第二種範例

完成 😎

程式碼

1
2
3
4
5
6
7
8
9
10
11
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

高效演算法

1
2
3
4
5
6
7
8
9
class Solution:
    def hammingWeight(self, num: int) -> int:        
        weight = 0

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

        return weight

也許你也會想看看