二進位操作 計算bit1的數目 Number of 1 Bits_Leetcode #191
題目敘述
題目會給我們一個整數，要求我們計算出這個整數的二進位表示法裡面，有幾個bit1?
例如 5 = 二進位的 101 => 有2個 bit1，答案為2
測試範例
Example 1:
Input: n = 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.
Example 2:
Input: n = 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.
Example 3:
Input: n = 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.
約束條件
Constraints:
- The input must be a binary string of length
32.
Follow up: If this function is called many times, how would you optimize it?
演算法
可以透過向右平移和LSB檢查來實現一個高效能的線性時間演算法。
可以想像LSB上頭有一個探針，每讀到1個bit1，計數器就累加1，就著再向右平移一次，總共迭代、遞迴32次，最終的計數器累計值就是答案，也就是bit1 的總數。
程式碼 遞迴版本
class Solution:
def hammingWeight(self, n: int) -> int:
# Base case
if n == 0 :
return 0
# General case:
# hammingWeight(n)
# = hammingWeight(n / 2) + LSB
# = hammingWeight(n / 2) + odd bit
# = hammingWeight(n / 2) + ( n & 1)
# Python's right shift operator is >>
return (n & 1) + self.hammingWeight( n >> 1 )
複雜度分析
時間複雜度: O(32) = O(1)
線性掃描，從右到左掃描每個bit，總共耗時O(32) = O(1) = 常數級別
空間複雜度: O(32) = O(1)
從右到左掃描每個bit，遞迴深度為O(32) = O(1) = 常數級別
程式碼 迭代版本
class Solution:
def hammingWeight(self, n: int) -> int:
num_of_1s = 0
for i in range(32):
num_of_1s += (n & 1)
n = n >> 1
return num_of_1s
時間複雜度: O(32) = O(1)
線性掃描，從右到左掃描每個bit，總共耗時O(32) = O(1) = 常數級別
空間複雜度: O(32) = O(1)
從右到左掃描每個bit，迭代長度為O(32) = O(1) = 常數級別
額外補充，Python 在3.10後的版本，提供內建函數，可以直接返回bit 1 count
(若在面試 或 上機考時，
仍然建議先寫出上方遞迴法或迭代法的演算法，來展現二進位操作的知識與能力)
class Solution:
def hammingWeight(self, n: int) -> int:
return n.bit_count()
關鍵知識點
從二進位的規律，想到用平移和 bitwiseAND 來計算一個二進位表示法裡面有幾個bit 1
Reference:
[1] Python/JS/Java/Go/C++ O( lg n ) by bit-manipulation - Number of 1 Bits - LeetCode
