【TIS-100 攻略】TIS-NET 第 6 關(guān)：信號(hào)預(yù)分頻器
本文首發(fā)于 B 站《TIS-100》文集（https://www.bilibili.com/read/readlist/rl626023）。原創(chuàng)不易，轉(zhuǎn)載請(qǐng)注明出處。
TIS-NET 第 6 關(guān)《信號(hào)預(yù)分頻器》（Signal Prescaler）關(guān)卡展示
本關(guān)要求將 IN 中的值依次除以 2、4、8，并將結(jié)果依次送往 OUT.2、OUT.4 和 OUT.8 端口。
注意到 IN 里的數(shù)都是 8 的倍數(shù)，所以我們可以先計(jì)算 8 分頻的值，將得到的結(jié)果乘以 2 就得到了 4 分頻的值，再乘以 2 就得到了 2 分頻的值。
另外，我在第 19 關(guān)《除法器》的攻略（傳送門：【TIS-100 攻略】第 19 關(guān)：除法器）里提過(guò)：除法可以使用【線性查找】和【二分查找】?jī)煞N方式來(lái)做。本關(guān)也一樣，我會(huì)用線性查找和二分查找這兩種方法各做一遍。
線性查找法（最省節(jié)點(diǎn)和代碼行數(shù)的做法）
核心思想是將 IN 里的值不斷減去 8，每減去一個(gè) 8 就令商加上 1，直到原值減到 0 為止，此時(shí)的商就是?8 分頻的值。之后將這個(gè)值乘以 2 得到 4 分頻的值，再乘以 2 得到 2 分頻的值。代碼如下：
左側(cè)的三個(gè)節(jié)點(diǎn)純傳話（mov up down, mov up down, mov up left）。然后看 OUT.2 上方的節(jié)點(diǎn)：
將 in 中的值放到 acc 里（mov left acc），
每次循環(huán)令 bak 加上 1（swp）
（add 1）
（swp）
以及令 acc 減去 8（sub 8）。
acc 尚未減到 0 時(shí)，跳回第 2 行繼續(xù)循環(huán)（jnz 2），
直到 acc 到達(dá) 0 為止，bak 中的值就是 8 分頻的值，將它發(fā)給右邊的節(jié)點(diǎn)（swp）
（mov acc right）
將 8 分頻的值乘以 2 后（add acc）
得到 4 分頻的值，同樣發(fā)給右邊的節(jié)點(diǎn)（mov acc right）。
將 4 分頻的值乘以 2 后（add acc）
得到 2 分頻的值，發(fā)給自己下方的 OUT.2 端口（mov acc down）。
OUT.4 上方的節(jié)點(diǎn)會(huì)從左邊依次收到 8 分頻和 4 分頻的值，將前者傳給右邊（mov left right），后者發(fā)到自己下方的 OUT.4 端口（mov left down）。
OUT.8 上方的節(jié)點(diǎn)會(huì)從左邊收到 8 分頻的值，將它發(fā)到自己下方的 OUT.8 端口（mov left down）。
點(diǎn)擊左下角的【RUN】，稍等片刻，便會(huì)彈出結(jié)算界面：
二分查找法（運(yùn)行速度最快的做法）
由于 IN 里的值必為 8 的倍數(shù)，且最多為 3 位數(shù)，所以 IN 里的最大有效值為 8×124=992，最大的 8 分頻值為 124，位于 0~127 范圍內(nèi)。因此，使用二分查找，每次將商的取值范圍縮小一半，最多經(jīng)過(guò) 7 次計(jì)算即可得到答案。步驟如下：
從 IN 里讀入一個(gè)數(shù)，設(shè)它為 a。檢查 a 是否大于等于 512。若是，則令 a 減去 512，同時(shí)令商加上 64（64×8=512，所以此時(shí)的 a 至少能商 64）；若否，則什么也不做。
檢查 a 是否大于等于 256。若是，則令 a 減去 256，同時(shí)令商加上 32（32×8=256，所以此時(shí)的 a 至少能商 32）；若否，則什么也不做。
檢查 a 是否大于等于 128。若是，則令 a 減去 128，同時(shí)令商加上 16（16×8=128，所以此時(shí)的 a 至少能商 16）；若否，則什么也不做。
檢查 a 是否大于等于 64。若是，則令 a 減去 64，同時(shí)令商加上 8（8×8=64，所以此時(shí)的 a 至少能商 8）；若否，則什么也不做。
檢查 a 是否大于等于 32。若是，則令 a 減去 32，同時(shí)令商加上 4（4×8=32，所以此時(shí)的 a 至少能商 4）；若否，則什么也不做。
檢查 a 是否大于等于 16。若是，則令 a 減去 16，同時(shí)令商加上 2（2×8=16，所以此時(shí)的 a 至少能商 2）；若否，則什么也不做。
檢查 a 是 0 還是 8。若是 8，則令商加上 1，否則商不變。此時(shí)的商就是 8 分頻的值。
本關(guān)的代碼如下：
由于用到的節(jié)點(diǎn)數(shù)量過(guò)多，我在圖上將用到的節(jié)點(diǎn)都編了號(hào)，并且用箭頭標(biāo)識(shí)出了數(shù)據(jù)流向。這次的數(shù)據(jù)是按蛇形流動(dòng)的。
1~6 號(hào)節(jié)點(diǎn)用于負(fù)責(zé) 7 次二分查找。6 個(gè)節(jié)點(diǎn)要做 7 次運(yùn)算，根據(jù)抽屜原理，至少有一個(gè)節(jié)點(diǎn)要做其中的 2 次運(yùn)算。這里我選擇了讓 1 號(hào)節(jié)點(diǎn)做前兩步運(yùn)算：
從 IN 里讀入一個(gè)數(shù)，視它為 a。檢查 a 是否大于等于 512，即 a-512（mov -512 acc）
（add up）是否大于等于 0。
大于等于 0 時(shí)按順序執(zhí)行，小于 0 時(shí)跳到第 6 行執(zhí)行（jlz 6）。
a-512 大于等于 0 時(shí)，令商加上 64，將增量 64 傳給 2 號(hào)節(jié)點(diǎn)（mov 64 down）
（jmp 8）
否則將增量 0 傳給 2 號(hào)節(jié)點(diǎn)（mov 0 down）
并將 a-512 還原成 a（add 512）。
檢查 a 是否大于等于 256，即 a-256（sub 256）是否大于等于 0。
大于等于 0 時(shí)按順序執(zhí)行，小于 0 時(shí)跳到第 12 行執(zhí)行（jlz c）。
a-256 大于等于 0 時(shí)，令商加上 32，將增量 32 傳給 2 號(hào)節(jié)點(diǎn)（mov 32 down）
（jmp e）
否則將增量 0 傳給 2 號(hào)節(jié)點(diǎn)（mov 0 down）
并將 a-256 還原成 a（add 256）。
操作完畢后，將處理后的 a 發(fā)給 2 號(hào)節(jié)點(diǎn)（mov acc down）。
2 號(hào)節(jié)點(diǎn)執(zhí)行的是第 3 步運(yùn)算：
1 號(hào)節(jié)點(diǎn)會(huì)將前兩次商的增量 q、dq 發(fā)來(lái)，我們計(jì)算出兩者之和（mov up acc）
（add up）
發(fā)給 3 號(hào)節(jié)點(diǎn)（mov acc right）
然后 1 號(hào)節(jié)點(diǎn)會(huì)發(fā)來(lái)最新的 a 值，我們檢查 a 是否大于 128，即 a-128（mov up acc）
（sub 128）是否大于等于 0。
大于等于 0 時(shí)按順序執(zhí)行，小于 0 時(shí)跳到第 9 行執(zhí)行（jlz 9）。
a-128 大于等于 0 時(shí)，令商加上 16，將增量 16 傳給 3 號(hào)節(jié)點(diǎn)（mov 16 right）
（jmp b）
否則將增量 0 傳給 3 號(hào)節(jié)點(diǎn)（mov 0 right），
并將 a-128 還原成 a（add 128）。
操作完畢后，將處理后的 a 發(fā)給 3 號(hào)節(jié)點(diǎn)（mov acc right）。
3 號(hào)節(jié)點(diǎn)執(zhí)行的是第 4 步運(yùn)算：
2 號(hào)節(jié)點(diǎn)會(huì)發(fā)來(lái)一個(gè)老的商值 q 和一個(gè)增量值 dq，我們計(jì)算出兩者之和，作為新的商（mov left acc）
（add left）
發(fā)給 4 號(hào)節(jié)點(diǎn)（mov acc right）。
然后 2 號(hào)節(jié)點(diǎn)會(huì)發(fā)來(lái)最新的 a 值，我們檢查 a 是否大于 64，即 a-64（mov left acc）
（sub 64）是否大于等于 0。
大于等于 0 時(shí)按順序執(zhí)行，小于 0 時(shí)跳到第 9 行執(zhí)行（jlz 9）。
a-64 大于等于 0 時(shí)，令商加上 8，將增量 8 傳給 4 號(hào)節(jié)點(diǎn)（mov 8?right）
（jmp b）
否則將增量 0 傳給 4 號(hào)節(jié)點(diǎn)（mov 0 right），
并將 a-64?還原成 a（add 64）。
操作完畢后，將處理后的 a 發(fā)給 4 號(hào)節(jié)點(diǎn)（mov acc right）。
4 號(hào)節(jié)點(diǎn)執(zhí)行的是第 5 步運(yùn)算：
3 號(hào)節(jié)點(diǎn)會(huì)發(fā)來(lái)一個(gè)老的商值 q 和一個(gè)增量值 dq，我們計(jì)算出兩者之和，作為新的商（mov left acc）
（add left）
發(fā)給 5?號(hào)節(jié)點(diǎn)（mov acc right）。
然后 3?號(hào)節(jié)點(diǎn)會(huì)發(fā)來(lái)最新的 a 值，我們檢查 a 是否大于 32，即 a-32（mov?left?acc）
（sub 32）是否大于等于 0。
大于等于 0 時(shí)按順序執(zhí)行，小于 0 時(shí)跳到第 9 行執(zhí)行（jlz 9）。
a-32?大于等于 0 時(shí)，令商加上 4，將增量 4?傳給 5?號(hào)節(jié)點(diǎn)（mov 4?right）
（jmp b）
否則將增量 0 傳給 5?號(hào)節(jié)點(diǎn)（mov 0 right），
并將 a-32?還原成 a（add?32）。
操作完畢后，將處理后的 a 發(fā)給 5 號(hào)節(jié)點(diǎn)（mov acc right）。
5 號(hào)節(jié)點(diǎn)執(zhí)行的是第 6 步運(yùn)算：
4 號(hào)節(jié)點(diǎn)會(huì)發(fā)來(lái)一個(gè)老的商值 q?和一個(gè)增量值 dq，我們計(jì)算出兩者之和，作為新的商（mov left acc）
（add left）
發(fā)給 6?號(hào)節(jié)點(diǎn)（mov acc?down）。
然后 4?號(hào)節(jié)點(diǎn)會(huì)發(fā)來(lái)最新的 a 值，我們檢查 a 是否大于 16，即 a-16（mov?left?acc）
（sub 16）是否大于等于 0。
大于等于 0?時(shí)按順序執(zhí)行，小于 0 時(shí)跳到第 9 行執(zhí)行（jlz 9）。
a-16?大于等于 0 時(shí)，令商加上 2，將增量 2?傳給 6?號(hào)節(jié)點(diǎn)（mov 2?down）
（jmp b）
否則將增量 0?傳給 6 號(hào)節(jié)點(diǎn)（mov 0 down），
并將 a-16?還原成 a（add?16）。
操作完畢后，將處理后的 a 發(fā)給 6?號(hào)節(jié)點(diǎn)（mov acc down）。
6 號(hào)節(jié)點(diǎn)執(zhí)行的是第 7 步運(yùn)算。注意這個(gè)節(jié)點(diǎn)是收尾節(jié)點(diǎn)，所以邏輯和前輩們不完全一樣：
5 號(hào)節(jié)點(diǎn)會(huì)發(fā)來(lái)一個(gè)老的商值 q 和一個(gè)增量值 dq，我們計(jì)算出兩者之和，作為新的商（mov up acc）
（add up）
放入 bak 中暫存（sav）。
然后 5 號(hào)節(jié)點(diǎn)會(huì)發(fā)來(lái)最新的 a 值（mov up acc），我們檢查 a 是 0 還是 8。
a 是 0 時(shí)按順序執(zhí)行，a 是 8 時(shí)跳到第 8 行執(zhí)行（jnz 8）。
a 是 0 時(shí)，商自身就是 8 分頻的值，只需拿出 bak（swp）
準(zhǔn)備輸出即可（jmp a）；
a 是 8 時(shí)，需要在原商的基礎(chǔ)上加 1（swp）
才能得到正確的 8 分頻值（add 1）。
我們將 8 分頻值復(fù)制一份給 7 號(hào)節(jié)點(diǎn)后（mov acc left），
再輸出到 OUT.8 口（mov acc down）。
7 號(hào)節(jié)點(diǎn)在得到 6 號(hào)節(jié)點(diǎn)發(fā)來(lái)的 8 分頻值后，將它乘以 2 得到 4 分頻的值（mov right acc, add acc），然后將這個(gè) 4 分頻的值復(fù)制一份給 8 號(hào)節(jié)點(diǎn)后，再輸出到 OUT.4 口（mov acc left, mov acc down）。
8 號(hào)節(jié)點(diǎn)在得到 7 號(hào)節(jié)點(diǎn)發(fā)來(lái)的 4 分頻值后，將它乘以 2 得到 2 分頻的值（mov right acc, add acc）并輸出到 OUT.2 口（mov acc down）。
點(diǎn)擊左下角的【RUN】，稍等片刻，便會(huì)彈出結(jié)算界面：
第 19 關(guān)除法器的攻略里我就提到了二分除法，但是效率僅僅提升了 3 倍。那是因?yàn)楸怀龜?shù)只有兩位數(shù)，即使用線性查找慢慢找也不會(huì)過(guò)于費(fèi)時(shí)。但是本關(guān)的被除數(shù)幾乎都是三位數(shù)，線性查找和二分查找的效率差異一下就被放大了：線性查找的話，商是多大，就需要進(jìn)行多少次運(yùn)算，本題里消耗了?13454 周期；而二分查找的話，只要商在 0~127 范圍內(nèi)，不管商是多少，都是雷打不動(dòng)的 7 次運(yùn)算，本題里只消耗了?660 周期，兩者的效率相差了兩個(gè)數(shù)量級(jí)！
