【TIS-100 攻略】TIS-NET 第 19 關(guān)：十進(jìn)制轉(zhuǎn)八進(jìn)制轉(zhuǎn)換器
本文首發(fā)于 B 站《TIS-100》文集（https://www.bilibili.com/read/readlist/rl626023）。原創(chuàng)不易，轉(zhuǎn)載請(qǐng)注明出處。
TIS-NET 第 19 關(guān)《十進(jìn)制轉(zhuǎn)八進(jìn)制轉(zhuǎn)換器》（Decimal to Octal Coverter）關(guān)卡展示
本關(guān)需要把收到的十進(jìn)制數(shù)轉(zhuǎn)成八進(jìn)制的形式輸出。八進(jìn)制即【逢 8 進(jìn) 1】，十進(jìn)制下逢 10 進(jìn) 1 的規(guī)則在八進(jìn)制下變成了逢 8 進(jìn) 1，舉例說明：十進(jìn)制的 7 在八進(jìn)制下也是 7，但十進(jìn)制的 8，由于觸發(fā)了逢 8 進(jìn) 1 的規(guī)則，在八進(jìn)制下會(huì)產(chǎn)生進(jìn)位，變成 10。類似的道理，十進(jìn)制下的 64，八八六十四，低位進(jìn)了 8 次位后，高位變成了 8 也會(huì)向它的更高位進(jìn) 1，所以十進(jìn)制的 64 在八進(jìn)制下需要用三位數(shù)表示，即 100。
本關(guān)的輸入量在 0~63 之間，所以輸出的八進(jìn)制最多也只有兩位數(shù)。由于逢 8 進(jìn) 1，所以八進(jìn)制的高位其實(shí)表示的是【這個(gè)數(shù)里有多少個(gè) 8】。也就是說這其實(shí)又是道除法題，高位是原數(shù)除以 8 的商，低位則是對(duì)應(yīng)的余數(shù)。
除法嘛，老規(guī)矩，線性查找法和二分查找法各說一遍。
線性查找法
將原數(shù)不斷減去 8，每減去一個(gè) 8，就令答案的高位加上 1，直到減到負(fù)數(shù)為止。代碼如下：
上方和中央節(jié)點(diǎn)純傳話（mov up down, mov up down）。然后看左下角節(jié)點(diǎn)：
左下角的節(jié)點(diǎn)收到 IN 中的數(shù)字后（mov up acc），
不斷減 8（sub 8），判斷是否減到了負(fù)數(shù)。
若減到了負(fù)數(shù)，則跳到第 6 行執(zhí)行（jlz 6）。
尚未減到負(fù)數(shù)時(shí)，按順序執(zhí)行，向右邊發(fā)送 -1 信號(hào)（mov -1 right），
并跳回第 2 行繼續(xù)減（jmp 2）。
直到減到負(fù)數(shù)后，向右邊發(fā)送 1 信號(hào)（mov 1 right），
并將減到了負(fù)數(shù)的被除數(shù)發(fā)給右邊（mov acc right）。
現(xiàn)在看右下角節(jié)點(diǎn)：
右下角的節(jié)點(diǎn)先將 acc 初始化為 8（mov -2 acc）
（add 10）
然后聽從左邊節(jié)點(diǎn)的指令（jro left）。左邊發(fā)送 -1 時(shí)，說明原數(shù)減 8 尚未減到負(fù)數(shù)，我們往回跳 1 行，令八進(jìn)制的高位加 1（add 10）；
左邊發(fā)送 1 時(shí)，說明原數(shù)減到了負(fù)數(shù)，我們將這個(gè)負(fù)數(shù)加回一個(gè) 8 后，得到原數(shù)除以 8 的余數(shù)，將它作為八進(jìn)制數(shù)的低位。由于初始值已經(jīng)將低位置為了 8，所以直接加上左邊發(fā)來的負(fù)數(shù)，就把最終的低位設(shè)置好了（add left）。
最后，將計(jì)算好的八進(jìn)制數(shù)發(fā)往下方的 OUT 口（mov acc down）。
點(diǎn)擊左下角的【RUN】，稍等片刻，便會(huì)彈出結(jié)算界面：
二分查找法
由于原始數(shù)字在 0~63 范圍，除以 8 的商在 0~7 范圍，二分查找法最多計(jì)算? 次即可得出結(jié)論。算法如下：
設(shè)原始數(shù)字為 a。
若 a >= 32，則令 b = a-32，令八進(jìn)制的高位加上 4，否則令 b = a；
若 b >= 16，則令 c = b-16，令八進(jìn)制的高位加上 2，否則令 c = b；
若?c >= 8，則令 d?= c-8，令八進(jìn)制的高位加上 1，否則令 d = c；
將八進(jìn)制的低位置為 d?并輸出。
代碼如下：
先看左下角的節(jié)點(diǎn)：
左下角的節(jié)點(diǎn)首先計(jì)算 a-32 的值（mov -32 acc）
（add up）
然后檢查該值是否小于?0：若該值小于 0，則令 b = a（acc 相當(dāng)于 b-32），同時(shí)八進(jìn)制的高位不變?，F(xiàn)在的 acc 是 b-32 的值，為了將 acc 變?yōu)?b-16，我們需要跳到第 6 行，將 acc 加回一個(gè) 16（jlz 6, add 16）。
若該值大于等于 0，則令 b = a-32（acc 已經(jīng)是 b），同時(shí)需要令八進(jìn)制的高位加上 4。我們向右邊發(fā)送 -2 信號(hào)，令右邊將八進(jìn)制的高位加上 4（mov -2 right）。
同時(shí)，因?yàn)橄乱徊揭卸?b 是否大于等于 16，即 b-16 是否大于等于 0，我們需要提前將 acc 表示的 b 減去 16（sub 32）
（add 16）
接下來判斷 b-16 是否小于?0：若該值小于 0，則令 c = b（acc 相當(dāng)于 c-16），同時(shí)八進(jìn)制的高位不變。現(xiàn)在的 acc 是 c-16 的值，為了將 acc 變?yōu)?c-8，我們需要跳到第 10 行，將 acc 加回一個(gè) 8（jlz a, add 8）。
若該值大于等于 0，則令 c = b-16（acc 已經(jīng)是 c），同時(shí)需要令八進(jìn)制的高位加上 2。我們向右邊發(fā)送 -1 信號(hào)，令右邊將八進(jìn)制的高位加上 2（mov -1 right）。
同時(shí)，因?yàn)橄乱徊揭卸?c 是否大于等于 8，即 c-8 是否大于等于 0，我們需要提前將 acc 表示的 c 減去 8（sub 16）
（add 8）
接下來判斷 c-8 是否小于?0：若該值小于 0，則令 d = c（acc 相當(dāng)于 d-8），同時(shí)八進(jìn)制的高位不變。因?yàn)榫o接著要發(fā)送的 acc 是 d-8 的值，我們跳到第 14 行（jlz e），先向右邊發(fā)送一個(gè) 2 信號(hào)，令右邊提前加上一個(gè) 8（mov 2 right），然后再將這個(gè) d-8 的值發(fā)給右邊，讓右邊順理成章地將八進(jìn)制的低位設(shè)置為 8+d-8=d 的值（mov acc right）。
若該值大于等于 0，則令 d = c-8（acc 已經(jīng)是 d），同時(shí)需要令八進(jìn)制的高位加上 1。我們向右邊發(fā)送 1 信號(hào)，令右邊將八進(jìn)制的高位加上 1，再將低位設(shè)置為 d（mov 1 right, jmp f, mov acc right）。
右下角的節(jié)點(diǎn)：開幕跳到第 4 行（jmp 4）的 jro 指令處（jro left），然后會(huì)收到左邊發(fā)來的 4 種指令中的 1 種。之前解釋左下角節(jié)點(diǎn)的代碼時(shí)都說過了，這里再匯總一下：
收到 -2 時(shí)，令八進(jìn)制的高位加上 4，此時(shí)我們往上跳 2 行，將 acc 加上 40（add 20, add 20）；
收到 -1 時(shí)，令八進(jìn)制的高位加上 2。此時(shí)我們往上跳 1 行，將 acc 加上 20（add 20）；
收到 1 時(shí)，令八進(jìn)制的高位加上 1，且已知接下來收到的是 d 值。此時(shí)我們往下跳 1 行，將 acc 加上 10（add 2, add 8），再加上接下來發(fā)來的 d 值并輸出給 OUT 口（add left, mov acc down）；
收到 2 時(shí)，八進(jìn)制的高位不變，且已知接下來收到的是 d-8 的值。此時(shí)我們向下跳 2 行，將 acc 提前加上 8（add 8），再加上接下來發(fā)來的 d-8，成功將低位置為 d 后，輸出給 OUT 口（add left, mov acc down）。
點(diǎn)擊左下角的【RUN】，稍等片刻，便會(huì)彈出結(jié)算界面：
