位元加法


Posted by cwc329 on 2020-06-21

因為有同學跑來問我,並且給我建議可以打成筆記,我就稍微紀錄一下我解題的想法還有過程。

位元加法

看到這個東西我的第一步是:
打開 Lidemy.com 看 CS101 的位元單元, 因為這部分我當初根本沒有仔細看。
這邊最重要的事情就是:

'位元是二進位'.repeat(3)

很重要所以要說三次。
所以我就直接用二進位加法的概念來解這題。

二進位加法

二進位加法很好寫。
想像直式加法,先對齊位數,然後由右到左一個位數一個位數加上去,就是這麼簡單。
而二進位只有10種數字,所以每個位數運算加法時會遇到100種狀況。
如果對上面這句話理解沒有問題,再加上直式運算,你應該可以理解二進位加法。
但是不能用 +-*/ 就不是這麼一回事了。
這邊一般會用到位元運算子,JS 的位元運算子會有 &、^、| 等符號,詳細要怎麼用可以去 google。
我會說去 google 是因為我沒有用到位元運算子。
為甚麼呢?
因為我在解題的時候裝了 Eslint,會擋位元運算子。
再加上我懶,懶到連去找怎麼 allow 都覺得麻煩,想說直接硬幹,事實證明乖乖去找怎麼 allow 可能比較好。
就如之前所說,每個位數會有100種狀況,也就是(0, 0)、(1, 0)、(1, 1)、(0, 1) 100 種組合,
所以不用 +-*/,組合數不多,可以用條件判斷來告訴在這 100 種組合下各自要做什麼動作:

  1. (0, 0) 寫 0,不用進位。
  2. (1, 0) 寫 1,不用進位。
  3. (1, 1) 寫 1,進位。
  4. (0, 1) 寫 1,不用進位。

寫到這邊突然發覺不對,我沒有考慮到前一個位數的進位。
然後再仔細觀察,(0,1) 與 (1, 0) 的結果是相同的,所以條件判斷應該可以改成:

  1. (0, 0)
    1. 上個數有進位。寫 1,不進位。
    2. 上個數沒進位。寫 0,不進位。
  2. (1, 0) || (0, 1)
    1. 上個數有進位。寫 0,進位。
    2. 上個數沒進位。寫 1,不進位
  3. (1, 1)
    1. 上個數有進位。寫 1,進位。
    2. 上個數沒進位。寫 0,進位。

在問了輸入範圍是 0 < N < 1000 後,我第一個想到的方法是把輸入用 Number.toString(2) 把數字轉成二進位字串。
這個時候有趣的問題來了,如果我由右往左一個一個取兩個字串的字,比較小的數字可能會比較快取完,這樣我的加法邏輯就會出問題。
所以我把數字轉成二進位字串之後,再用 String.padStart(32, 0) 讓兩個字串的長度相同。
本來這樣在加上 for 迴圈應該就可以快意解題了,但是竟然連 +=、-= 都不能用,我該如何是好?
我的解決方法是改用 while 迴圈,但是條件判斷該怎麼辦呢?
初心者如我最熟悉的東西式陣列,那我就想說轉成陣列來處理吧,反正最多不過就兩個長度 32 的陣列,不會有太多問題。
轉成陣列後先用Array.reverse()反轉陣列,我就可以用 Array.shift() 從第一個把位數取出來相加。
這樣做同時會逐步縮短陣列長度,我就可以在 while 迴圈條件設定當陣列長度為 0 時結束迴圈。
然後宣告一些變數儲存東西, result = ''紀錄答案,不過因為我不知道怎麼用 += 以外的方法在字串尾巴放東西,於是我就找我的好朋友陣列result = [],這樣就可以用result.push()把結果 push 進去。
還有宣告Adddigit = 0做為紀錄是否進位。
當迴圈結束,我也把所有結果都記錄好了,那我就可以取用 result 中的東西。
因為我是從最右邊的加法結果開始 push,所以這邊要先反轉陣列,然後再把陣列 join,最後再把二進位字串轉換成數字。
最後的結果就會是answer = parseInt(result.reverse().join(''), 2)
以上就是我落落長的解題過程。

我的程式碼










Related Posts

[Py 百日馬 Day 0] 來場 Python 百日馬吧!

[Py 百日馬 Day 0] 來場 Python 百日馬吧!

React 基礎:環境建置篇

React 基礎:環境建置篇

Day 139

Day 139


Comments