題目描述
請實現(xiàn)一個函數(shù)趾撵，輸入一個整數(shù)，輸出該數(shù)二進(jìn)制表示中 1 的個數(shù)勋拟。例如妈候，把 9 表示成二進(jìn)制是 1001挂滓，有 2 位是 1赶站。因此，如果輸入 9想括，則該函數(shù)輸出 2。
示例
示例 1：
輸入：00000000000000000000000000001011
輸出：3
解釋：輸入的二進(jìn)制串 00000000000000000000000000001011 中瑟蜈，共有三位為 '1'。
示例2：
輸入：00000000000000000000000010000000
輸出：1
解釋：輸入的二進(jìn)制串 00000000000000000000000010000000 中宪躯，共有一位為 '1'位迂。
示例3：
輸入：11111111111111111111111111111101
輸出：31
解釋：輸入的二進(jìn)制串 11111111111111111111111111111101 中，共有 31 位為 '1'臣缀。
解答方法
方法一：位運算
思路
- 初始化數(shù)量統(tǒng)計變量 res = 0 泻帮。
- 循環(huán)逐位判斷： 當(dāng) n = 0時跳出刑顺。
- res += n & 1 ： 若 n& 1 = 1（末位為1） 蹲堂，則統(tǒng)計數(shù) res 加一狼讨。
- n >>= 1 ： 將二進(jìn)制數(shù)字 n 無符號右移一位 政供。
- 返回統(tǒng)計數(shù)量 res朽基。
代碼
class Solution:
def hammingWeight(self, n: int) -> int:
res = 0
while n:
res += n&1
n >>= 1
return res
時間復(fù)雜度
O(log n) ： 此算法循環(huán)內(nèi)部僅有 移位、與稼虎、加 等基本運算，占用 O(1) 哀军；逐位判斷需循環(huán) logn次杉适，其中 logn代表數(shù)字 n 最高位 11的所在位數(shù)（例如 log 4 = 2猿推、log16 = 4）蹬叭。
空間復(fù)雜度
O(1) ： 變量 res使用常數(shù)大小額外空間。
方法二：n&(n-1)
思路
一個數(shù) n 與一個比它小 1 的數(shù)（n?1）進(jìn)行與運算（&）之后侈离，得到的結(jié)果會消除 n 中最低位的 1.
代碼
class Solution:
def hammingWeight(self, n: int) -> int:
res = 0
while n:
res +=1
n = n&(n-1)
return res
時間復(fù)雜度
O(M)： n&(n?1) 操作僅有減法和與運算卦碾，占用 O(1) 起宽；設(shè) MM 為二進(jìn)制數(shù)字 n 中 1 的個數(shù)，則需循環(huán) M 次（每輪消去一個 1 ）绿映，占用 O(M) 叉弦。
空間復(fù)雜度
O(1) ： 變量 res 使用常數(shù)大小額外空間淹冰。
