二進位操作 計算bit1的數目 Number of 1 Bits_Leetcode #191

Marcel Eberle on Unsplash

題目敘述

題目會給我們一個整數，要求我們計算出這個整數的二進位表示法裡面，有幾個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