Leetcode 1404. Number of Steps to Reduce a Number in Binary Representation to One
這幾天的 Leetcode Daily 剛好都是一些 bitwise 相關的題目。剛好這一題從一開始的解法到後來的思路都很有意思，值得寫一篇來分享。
題目
1404. Number of Steps to Reduce a Number in Binary Representation to One
大意上是說，題目會給定一個 Binary Representation String，而用戶有兩種操作：
- 該 String 代表的是偶數，則除 2
- 該 String 為奇數，則加 1
直到最後是 1 時，計算共需要幾步驟。
解題思路
最直覺的想法是：把該 binary representation string 轉成 integer，然後照上面的條件去跑；但很可惜，給定題目中的 string.length <= 500。
模擬法
我們知道，對於一個 binary representation string 而言：
- 除 2：相當於往右 Shift 一個 bit
- 加 1：相當於從右往左，找到首個不是
1的 bit，將其改為 1，然後把後面的全部設成0
舉例來說：
"1000" (8) -> "100" (4) -> "10" (2) -> "1" (1) // 除 2
"1101" (13) -> "1110" (14)
照著這個思路，我們可以用 Go 實作（因為 go slice 操作上比 C array 簡單，這邊用 go 偷懶一下 XD）：
func numSteps(s string) (ans int) {
for s != "1" {
ans++
if s[len(s)-1] == '0' {
s = div2(s)
} else {
s = add1(s)
}
}
return
}
func div2(s string) string {
return s[:len(s)-1]
}
func add1(s string) string {
runes := []rune(s)
for i := len(s)-1; i >= 0; i-- {
if runes[i] == '1' {
runes[i] = '0'
} else {
runes[i] = '1'
break;
}
}
if runes[0] == '0' {
runes = append([]rune{'1'}, runes...)
}
return string(runes)
}
- Runtime: 3ms (20%)
- Memory: 5.94 MB (5%)
這顯然是不夠好。從小學二年級的知識中，我們知道：string 在 Go 的設計中是不可變的（immutable），這代表著每次對 string 執行的操作將會複製一次該值，這個缺點在 div2 函式中被放大。
另一方面，每一次呼叫 add1 時都會將 string 轉為 []rune，這顯然也是不利於效能的，於是我們可以換個做法：
func numSteps(s string) (ans int) {
runes := []rune(s)
for len(runes) > 1 {
ans++
if runes[len(runes)-1] == '0' {
runes = div2(runes)
} else {
runes = add1(runes)
}
}
return
}
func div2(s []rune) []rune {
return s[:len(s)-1]
}
func add1(s []rune) []rune {
for i := len(s)-1; i >= 0; i-- {
if s[i] == '1' {
s[i] = '0'
} else {
s[i] = '1'
break;
}
}
if s[0] == '0' {
s = append([]rune{'1'}, s...)
}
return s
}
- Runtime: 1ms (70%)
- Memory: 2.32MB (10%)
稍微是把 Runtime 壓下來一點點，但 Memory 的使用情況仍不是很理想。我們可以將 []rune 改為 []byte，這可以進一步壓低記憶體用量；這是因為 rune 是 int32、byte 則是 uint8
題目給定的字串長度可能有 500 bits，因此我們無法以 int64 等內建的資料型態裝載；但內建的 math/big 函式庫卻能夠很好地協助我們解決這個問題。
func numSteps(s string) (ans int) {
n := big.NewInt(0)
n.SetString(s, 2)
for n.Cmp(big.NewInt(1)) != 0 {
tb := n.TrailingZeroBits()
if tb > 0 {
ans += int(tb)
n.Rsh(n, tb)
} else {
ans++
n.Add(n, big.NewInt(1))
}
}
return
}
直接利用內建套件，即可協助我們處理大整數的問題，同時也能有不錯的效能。
貪婪法
無論上面的思路如何改進，都會是一個時間複雜度為 $O(n^2)$ 的演算法，但實際上此處存在 $O(n)$ 方法。詳細可以參考 Leetcode 的題解，此處不過多贅述。
int numSteps(char* s) {
int n = strlen(s);
int op = 0, ca = 0;
for (int i = n-1; i > 0; i--) {
int d = s[i]-'0' + ca;
if (d%2) { op += 2; ca = 1; }
else { op++; }
}
return op + ca;
}
如果按照 Leetcode 的題解，可以寫出上述的程式，但在 if (d%2) 這段令我不是很滿意，我們知道 if (d%2) 等價於 if (d&1)（從 assembly 上也可以觀察到這件事）
然而，此處多做了一個 if else 判斷令我不是很滿意，多餘的分支判斷代表 CPU 可能會對其進行分支預測；即便近年來分支預測的能力不斷提升，但在可預期的改善路徑上如果可以避免分支也是很值得探討的。
因此，以上程式可以改寫為
int numSteps(char* s) {
int n = strlen(s);
int op = 0, ca = 0;
for (int i = n-1; i > 0; i--) {
int d = s[i]-'0' + ca;
op += (d & 1) + 1;
ca |= (d & 1);
}
return op + ca;
}
結論
我認為本次的嘗試是有趣的，從 Go 版本的 Simulation 到 C 版本的 Greedy，再輔以一些小技巧取得微乎其微（事實上，微不足道）的效能提升。
不過，正因為有這些嘗試，才讓人覺得這些挑戰是有趣的、值得思考的。