【TIS-100 攻略】第 8~9 關(guān)：信號(hào)突變檢測(cè)器、中斷處理器
本文首發(fā)于 B 站《TIS-100》文集（https://www.bilibili.com/read/readlist/rl626023）。原創(chuàng)不易，轉(zhuǎn)載請(qǐng)注明出處。
第 8 關(guān)《信號(hào)突變檢測(cè)器》（Signal Edge Detector）關(guān)卡展示
本關(guān)需要不斷從 IN 中讀取數(shù)據(jù)，僅當(dāng)本次數(shù)字和上次數(shù)字的絕對(duì)差值大于等于 10 時(shí)，才向 OUT 輸出 1，否則向 OUT 輸出 0。
本關(guān)和上一關(guān)類似，同樣需要將每一次的輸入值讀取兩遍，一遍用來(lái)計(jì)算和上次數(shù)字的差值，另一遍用來(lái)記住本次的值，用于在下一次任務(wù)里計(jì)算和本次的差值。本關(guān)的代碼如下：
上方節(jié)點(diǎn)和中央節(jié)點(diǎn)全部只用來(lái)傳話（mov up down）。
左下角的節(jié)點(diǎn)收到 IN 傳來(lái)的值后，將它存入 acc（mov up acc），并將同樣的值向右發(fā)送兩遍（mov acc right, mov acc right）。接下來(lái)是右邊的節(jié)點(diǎn)：
首先將 acc 和左邊發(fā)來(lái)的值做差值運(yùn)算（sub left）。
然后檢查差值是否小于 -9，即差值加上 9（add 9）后是否小于 0。
若差值小于 0，則跳到第 8 行執(zhí)行（jlz 8），否則按順序執(zhí)行。代碼里 add 9 和 sub left 誰(shuí)先誰(shuí)后不影響結(jié)果的正確性，截圖里之所以先 add 9 再 sub left，是因?yàn)?sub left 這條指令需要等待數(shù)據(jù)從左側(cè)節(jié)點(diǎn)傳來(lái)。這樣的話，與其干等，不如先把 add 9 這一步做了，后面就不用做了，這樣可以節(jié)省總體的運(yùn)行時(shí)間。
上面我們已經(jīng)判斷了差值是否小于 -9，而且如果滿足條件的話就已經(jīng)跳到了第 8 行了。如果還停留在第 4 行的話，說(shuō)明差值是不小于 -9 的，那么我們還要進(jìn)一步判定差值是否大于 9，即差值 -9 是否大于 0?，F(xiàn)在 acc 里的值是差值 +9，我們現(xiàn)在要令 acc 減去?18，令它變成差值 -9（sub 18），然后判斷此時(shí)的 acc 是否大于 0。
若大于 0，則同樣跳到第 8 行執(zhí)行（jgz 8）。
兩條有條件跳轉(zhuǎn)指令都指向了第 8 行這同一個(gè)跳轉(zhuǎn)點(diǎn)，說(shuō)明這是一個(gè)【或】邏輯，兩個(gè)條件中任意一個(gè)成立，都跳轉(zhuǎn)到這個(gè)位置去執(zhí)行。如果此時(shí)還停留在第 6 行，就說(shuō)明【差值 < -9】和【差值 > 9】這兩個(gè)條件都不滿足，此時(shí)直接向 OUT 口輸出 0（mov 0 down），
并強(qiáng)制跳到第 9 行，無(wú)視第 8 行代碼（jmp 9）。
接下來(lái)是第 8 行，只要滿足【差值 < -9】和【差值 > 9】中的任意一條，就會(huì)來(lái)到這里，向 OUT 口輸出 1（mov 1 down）。
輸出完成后，我們讀取左邊節(jié)點(diǎn)第二次發(fā)來(lái)的 IN 值，并放入 acc 中，用作下一次計(jì)算差值的依據(jù)（mov left acc）。
點(diǎn)擊左下角的【RUN】，稍等片刻，便會(huì)彈出結(jié)算界面：
第 9 關(guān)《中斷處理器》（Interrupt Handler）關(guān)卡展示
這是我們遇到的第一個(gè)難度比較大的關(guān)卡。這一關(guān)一共有 4 路輸入，每一路輸入信號(hào)都只會(huì)是 0 或 1。本關(guān)要求，任何一路由 0 跳變成 1 時(shí)，視為這一路發(fā)生了中斷，我們需要將發(fā)生中斷的路數(shù)發(fā)送給 OUT。當(dāng)沒(méi)有任何中斷出現(xiàn)時(shí)，向 OUT 發(fā)送 0。題目保證不會(huì)有多路信號(hào)同時(shí)發(fā)生跳變。
看到這個(gè)題目，你的第一反應(yīng)可能還是沿襲上一關(guān)的思路：將本次輸入信號(hào)發(fā)送兩遍給鄰居節(jié)點(diǎn)，由鄰居節(jié)點(diǎn)計(jì)算差值決定要往輸出口輸出多少……
但是本關(guān)是四路輸入信號(hào)，信號(hào)如何匯總是個(gè)大問(wèn)題，更何況左下角還有一個(gè)損壞的節(jié)點(diǎn)，我們根本沒(méi)法用那么多輔助節(jié)點(diǎn)，把每一路的輸入信號(hào)都存下來(lái)，然后往下發(fā)兩遍……
不過(guò)，有個(gè)條件我們可以利用一下，就是輸入信號(hào)只有 0 和 1 兩種。因此，我們可以把代碼分成兩部分：前一次是 0 時(shí)要干的事，以及前一次是 1 時(shí)要干的事。這兩部分完全獨(dú)立，互不干擾。這樣就不需要用輔助節(jié)點(diǎn)把每次的輸入量存下來(lái)然后發(fā)兩遍了，我們直接用跳轉(zhuǎn)指令定位到對(duì)應(yīng)的代碼塊上就完事了。本關(guān)的代碼如下：
前一次的信號(hào)是 1 時(shí)，不論本次收到的是什么數(shù)字，都無(wú)腦往下發(fā) 0；
前一次的信號(hào)是 0 時(shí)，如果本次收到的還是 0，那么仍然往下發(fā) 0；
僅當(dāng)前一次的信號(hào)是 0，同時(shí)本次信號(hào)是 1 時(shí)，才往下發(fā)自己的路數(shù)。
上方的 4 個(gè)節(jié)點(diǎn)，除了最后一行發(fā)的路數(shù)分別是 1、2、3、4 外，其余代碼都完全一致。我們挑最左邊這個(gè)典型講。
第 1~3 行代碼是【前一次信號(hào)為 1】時(shí)要執(zhí)行的操作，第 4~6 行代碼是【前一次信號(hào)為 0】時(shí)要執(zhí)行的操作。由于第一次收到任何數(shù)字都需要往下發(fā) 0，所以我們不妨設(shè)第一次之前不存在的“前一次信號(hào)”為 1。
前一次信號(hào)為 1 時(shí)，我們先把本次信號(hào)給收了（mov up acc）。
然后不論本次信號(hào)是啥，都無(wú)腦往下傳 0（mov 0 down）。
到了這里，我們就需要根據(jù)本次收到的值來(lái)決定接下來(lái)停留在哪個(gè)代碼塊了。如果本次收到的值是 1，那么就跳回第 1 行，把程序牢牢固定在第 1~3 行的代碼塊中（jgz 1）。如果本次收到的值是 0，那么就放任程序流淌到第 4~6 行的代碼塊中。
前一次信號(hào)為 0 時(shí)，我們同樣把本次信號(hào)收了（mov up acc），然后：
若本次信號(hào)仍是 0，則跳到第 2 行，往下傳 0（jez 2, mov 0 down），然后由于本次信號(hào)是 0，所以接下來(lái)的 jgz 1 判定是必然不成立的，程序短暫逃離后，又被吸回了第 4~6 行的代碼塊中。
若本次信號(hào)為 1，則因?yàn)樾盘?hào)由 0 變成了 1，我們需要把當(dāng)前的路數(shù)往下發(fā)（mov 1 down），發(fā)完后，程序會(huì)跳到第 1 行，也就是自動(dòng)來(lái)到了【前一次信號(hào)為 1】的代碼塊中。
第 2~4 路的代碼同理，只是發(fā)生中斷時(shí)，輸出的路數(shù)分別變成了 2、3、4。
下方的一排節(jié)點(diǎn)用于把上方這一排節(jié)點(diǎn)發(fā)的四個(gè)數(shù)字匯總到中間的 3 路節(jié)點(diǎn)上。1 路節(jié)點(diǎn)只會(huì)收到從上方發(fā)來(lái)的信號(hào)，無(wú)腦往右傳（mov up right）；4 路節(jié)點(diǎn)同樣只會(huì)收到上方發(fā)來(lái)的信號(hào)，無(wú)腦往左傳（mov up left）；2 路節(jié)點(diǎn)會(huì)收到上方和左方發(fā)來(lái)的信號(hào)，依次傳給右邊的 3 路節(jié)點(diǎn)（mov up right, mov left right）。3 路節(jié)點(diǎn)是所有信號(hào)的匯合點(diǎn)，它會(huì)從上方收到一個(gè)信號(hào)，從左方收到兩個(gè)信號(hào)，從右方收到一個(gè)信號(hào)。因?yàn)椴粫?huì)有多路中斷同時(shí)發(fā)生，所以這些信號(hào)中至多只有一個(gè)非 0 信號(hào)。我們只需要把這些信號(hào)加起來(lái)（mov up acc, add left, add right, add left），就能發(fā)現(xiàn)是哪路發(fā)生了中斷。我們直接將累加后的值往下發(fā)（mov acc down），委托下方的節(jié)點(diǎn)傳話給 OUT（mov up down），就完成了任務(wù)。
這里要注意一下我匯總各路信號(hào)的過(guò)程，先讀一次左路（add left），接著讀一次右路（add right），最后再讀一次左路（add left）。為什么我要使用這樣反復(fù)橫跳的讀取方式，而不用看起來(lái)更舒服的【讀完一邊再讀另一邊】的方式呢？因?yàn)樽舐返膬山M信號(hào)，一組是自己的，一組是從它的左邊傳來(lái)的。左邊的節(jié)點(diǎn)只有傳完了第一個(gè)信號(hào)，才會(huì)再?gòu)乃淖筮呑x取第二個(gè)信號(hào)傳給右邊。也就是，左路的兩個(gè)信號(hào)間有一定的時(shí)間差。為了效率最大化，我們選擇在這個(gè)時(shí)間差里讀取早已等候多時(shí)的右路信號(hào)，等到讀完右路信號(hào)后，左路的第二個(gè)信號(hào)正好也傳過(guò)來(lái)了。這樣我們的時(shí)間就一點(diǎn)都沒(méi)浪費(fèi)。
點(diǎn)擊左下角的【RUN】，稍等片刻，便會(huì)彈出結(jié)算界面：
要不是看到我的智乃醬比我的行數(shù)還少，我真的就以為我的行數(shù)是全球最優(yōu)的了。畢竟在直方圖最左端嘛。真不知道她的 23?行代碼是怎么做到的，比我還厲害。
優(yōu)化代碼行數(shù)
智乃醬出來(lái)了，告訴了我怎么才能寫出最省行數(shù)的代碼。最省行數(shù)的方法跟上一關(guān)的套路是一樣的，檢測(cè)本次發(fā)生了中斷的路數(shù)，和上一次的狀態(tài)值進(jìn)行比較，得出結(jié)論。
第 1 路直接將 IN.1 的信號(hào)往右傳（mov up right）。
第 2 路將 IN.2 的信號(hào)乘以 2（mov up acc, add acc），由 0/1 變成 0/2 后往右傳（mov acc right）。接著把左邊傳來(lái)的 1 路信號(hào)也往右傳（mov left right）。
第 4?路將 IN.4 的信號(hào)乘以 4（mov up acc, add acc, add acc），由 0/1 變成 0/4 后往右傳（mov acc left）。
最麻煩的是第 3 路。首先第 3 路需要將信號(hào)乘以 3，而我們使用 add acc 這樣的指令只能將原數(shù)乘以各種 2 的冪，3 不是 2 的冪，我們無(wú)法用這樣的方法得到原數(shù)乘以 3 的值。但由于輸入信號(hào)只有 0/1 兩種，所以我們使用按條件跳轉(zhuǎn)指令將原信號(hào)轉(zhuǎn)換成 0/3。具體做法如下：
首先我們將 IN.3 的信號(hào)存入 acc（mov up acc），
然后判斷該信號(hào)值是否為 0。該信號(hào)為 0 時(shí)，直接跳到第 4 行執(zhí)行，跳過(guò)第 3 行代碼（jez 4）。
僅當(dāng)原信號(hào)不為 0 時(shí)，我們才在原信號(hào)的基礎(chǔ)上 +2（add 2）。這樣我們就把 3 路信號(hào)由原始的 0/1 轉(zhuǎn)換成了 0/3。
從第 4 行開(kāi)始，我們把其他幾路傳來(lái)的信號(hào)加在了一起（add left），
（add right）
（add left）
并將累加后的信號(hào)往下傳兩遍（mov acc down, mov acc down）。和上一關(guān)的方案是同樣的道理，一遍用來(lái)計(jì)算和上次數(shù)字的差值，另一遍用來(lái)記住本次的值，用于在下一次任務(wù)里計(jì)算和本次的差值。
中央節(jié)點(diǎn)純粹帶路黨（mov up down）。下方節(jié)點(diǎn)的代碼跟上一關(guān)是差不多的，簡(jiǎn)單講一下：
首先將上一次的信號(hào)值和本次的信號(hào)值做差（sub up）。
若為負(fù)數(shù)，則跳到第 4 行執(zhí)行（jlz 4），否則按順序執(zhí)行。
上一次的信號(hào)值和本次的信號(hào)值之差為 0 或正數(shù)時(shí)，說(shuō)明本回合里沒(méi)有信號(hào)突變，或者本次的信號(hào)值更小，有一路信號(hào)從 1 變成了 0。此時(shí)我們只需簡(jiǎn)單清空 acc 即可（sub acc）。
上一次的信號(hào)值和本次的信號(hào)值之差為負(fù)數(shù)時(shí)，說(shuō)明本次的信號(hào)值更大，本回合里有一路信號(hào)從 0 變成了 1。此時(shí)我們對(duì)該負(fù)數(shù)取絕對(duì)值，得到由 0 跳變成了 1 的路數(shù)（neg）。注意：差值為非負(fù)數(shù)時(shí)，這條 neg 指令一樣會(huì)被執(zhí)行到，不過(guò)因?yàn)?0 的相反數(shù)仍是 0，所以這時(shí)候 neg 就相當(dāng)于空操作指令，兩條分支就得以共用代碼。
將 acc 值向下輸出（mov acc down）。
輸出完成后，我們讀取上方第二次發(fā)來(lái)的信號(hào)值，并放入 acc 中，用作下一次計(jì)算差值的依據(jù)（mov up?acc）。
點(diǎn)擊左下角的【RUN】，稍等片刻，便會(huì)彈出結(jié)算界面：
至此我們減少到了 24 行代碼。
能去掉 NEG 指令嗎？
我們注意到以上方案中，最后一行芯片輸出非 0 值前還需要給 acc 取個(gè)反再輸出。那么這個(gè)步驟能去掉嗎？答案是可以的，只要把上排節(jié)點(diǎn)輸出的值改一下就行了。之前輸出的信號(hào)值分別是 0/1、0/2、0/3、0/4，現(xiàn)在改成 0/-1、0/-2、0/-3、0/-4 就 OK 了。這樣做相當(dāng)于把取反的過(guò)程交給了上排節(jié)點(diǎn)。與此同時(shí)，下方節(jié)點(diǎn)的判斷也要改成【差值為負(fù)時(shí)輸出 0，差值為正或 0 時(shí)輸出 acc】，跟原來(lái)的判定條件正好反過(guò)來(lái)。
注意我圈出來(lái)了的做了改動(dòng)的地方。下方節(jié)點(diǎn)只是把判斷改成了正跳轉(zhuǎn)（jgz 4），并去掉了取反指令 neg。關(guān)鍵是上方節(jié)點(diǎn)。上方節(jié)點(diǎn)先讀 3 路信號(hào)（mov up acc），該信號(hào)值為 0 時(shí)直接跳到第 4 行（jez 4），信號(hào)值不為 0 時(shí)將該信號(hào)減去 4（sub 4）。由于 1 - 4 = -3，我們就這樣成功把 3 路的 0/1 信號(hào)處理成了 0/-3 信號(hào)。接下來(lái)，由于其他幾路傳來(lái)的仍然是 0/1、0/2、0/4 這樣的信號(hào)，所以我們要減去這些信號(hào)（sub left, sub right, sub left），相當(dāng)于把這些信號(hào)轉(zhuǎn)換成 0/-1、0/-2、0/-4 并累加。累加完成后，把累加后的信號(hào)向下傳兩遍（mov acc down, mov acc down）。
這樣改動(dòng)了一下以后，我們的代碼行數(shù)由 24?行減少到了 23?行，運(yùn)行時(shí)長(zhǎng)也由原先的 376 周期減少到了 375 周期。既然完爆了上一版方案，那上一版方案就沒(méi)有留著的必要了。
