合縱連橫: 從 二進位DP框架 來看整數有幾個bit1
這篇文章，會帶著大家複習以前學過的二進位DP框架，
並且以0~N的整數有幾個bit1，有幾個bit0的概念為核心，
貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個演算法框架。
常見的考法
請問整數k有幾個bit1? 有幾個bit0?
請問整數0到整數N分別各有幾個bit1? 有幾個bit0?
除了暴力法，有沒有更好的方法?
二進位的本質
比較大的數字都可以由比較小的數字平移(相當於乘法)與加法建造而來
如果N是奇數，那麼N可以由floor( N / 2) << 1 + 1 得到
例如5=0b 101
十進位的觀點:
5 = 2 * 2 + 1
二進位的觀點
101 = (10 << 1) + 1
5 可以由 floor( 5/2 ) << 1 + 1得到
相當於5 = 0b 10 << 1 + 0b 1 = 0b 100 + 0b 1 = 0b 101
如果N是偶數，那麼N可以由floor( N / 2) << 1 + 0 得到
例如6=0b 110
十進位的觀點:
6 = 2 * 3 + 0
二進位的觀點
110 = (11 << 1) + 0
6 可以由 floor( 6/2 ) << 1 + 0得到
相當於6 = 0b 11 << 1 + 0b 0 = 0b 110 + 0b 0 = 0b 110
整合在一起看，我們可以說
任意正整數N，可以用這個遞迴式子表達
N
= floor(N/2) << 1 + odd bit, where odd bit = 1 當N是奇數時，否則為0
= floor(N/2) << 1 + ( N & 1)
數整數N有幾個Bit1 Number of 1 Bits - LeetCode
承接剛剛上面的討論，我們可以定義DP[n] = 整數n有幾個bit1
那麼通則就是
DP[n] = DP[ floor(n / 2)] + n&1
初始條件呢? 也是就是說，什麼時候遞迴停下來?
很明顯，就是0，0就只有0，沒有任何bit1
DP[0] = 0 = 0b b
到這邊通則、初始條件都具備了，就可以來寫程式碼
時間複雜度: O( log2 n) 遞迴深度最深 log2 n次可以抵達初始條件停下來。
空間複雜度: O( log2 n) 遞迴深度最深 log2 n次可以抵達初始條件停下來。
數整數N有幾個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 )
接下來，再看進階一點的延伸題
整數0~N分別各有幾個Bit1 Counting Bits - LeetCode
在前一題，我們已經知道個別整數k的bit1計算方法，
DP定義、遞迴關係式、初始條件也都具備了。
這題相對來說，就只是套上一個迴圈的外衣而已，從0依序計算到整數N，
並且利用DP table把已經計算過的答案儲存起來，避免之後大整數遞迴時重複的計算。
時間複雜度: O( n) 遞迴深度最深 n次可以抵達初始條件停下來，
每層遞迴只要O(1)即可透過查表，快速在常數時間計算出這層的答案。
空間複雜度: O( n) 遞迴深度最深 n次可以抵達初始條件停下來。
數整數0~整數N有幾個Bit1 Top-down DP遞回程式碼
class Solution:
def countBits(self, n: int) -> List[int]:
dp = {}
def counting(i):
if i in dp:
# Look-up DP table
return dp[i]
if i == 0:
# Base case
dp[0] = 0
else:
# General cases
dp[i] = (i&1) + counting(i//2)
return dp[i]
#============================
return [ counting(i) for i in range(n+1) ]
數整數0~整數N有幾個Bit1 Bottom-up DP迭代程式碼
class Solution:
def countBits(self, n: int) -> List[int]:
## base case
# 0 = 0b 0
dp = [0]
## general cases
for i in range(1, n+1):
# even number = (n//2) << 1, with adding 0 on the LSB
# odd number = (n//2) << 1 + 1 = (n//2) << 1 | 1, with adding 1 on the LSB
dp.append( dp[ i//2] + (i & 1) )
return dp
結語
好，今天一口氣介紹了最精華的部分，
通用的二進位DP框架，還有相關的二進位結構應用題與演算法建造，
希望能幫助讀者、觀眾徹底理解它的原理，
並且能夠舉一反三，洞察其背後的本質和了解相關的應用領域！
感謝收看囉! 我們下篇文章再見~
