本文首發(fā)于 B 站《TIS-100》文集（https://www.bilibili.com/read/readlist/rl626023）。原創(chuàng)不易，轉(zhuǎn)載請注明出處。

TIS-NET 第 7 關(guān)《信號均值計算器》（Signal Averager）關(guān)卡展示

本關(guān)需要將 IN.A 和 IN.B 的均值，即 (a+b)/2 的值，發(fā)送給 OUT。當均值出現(xiàn)了小數(shù)時，向下取整，而不是四舍五入。

這里我們首先要解決的是【a+b 超過三位數(shù)怎么辦】的問題。TIS-100 里，每個節(jié)點的 acc 和 bak 里的數(shù)字都必須在 -999~999 的范圍內(nèi)，如果在計算的過程中發(fā)生了數(shù)值溢出，則結(jié)果會被自動替換為最近的邊界值。

所以，假如你從 IN.A 里收到了 777，從 IN.B 里收到了 888，然后你直接將兩者相加的話，acc 會變成 999 而不是期望的 1665。你在錯誤的中間結(jié)果上做除以 2?的運算，得到的最終結(jié)果也一定是錯誤的。一步錯，步步錯。

那么我們該怎么在不觸發(fā)溢出的前提下，正確得到 a+b 的值呢？這里我們要脫離思維定式，a 和 b 的平均值就非得用 (a+b)/2 來計算嗎？這里，我們設(shè)兩者中的較小值為 L，較大值為 R。那么求平均值的過程，就是 L 和 R 兩者不斷靠近的過程。L 每加上 1，R 就減去 1，直到兩者相遇或發(fā)生錯位為止。兩者每執(zhí)行一次上述動作，兩者間的距離就減少 2。因為兩者的初始距離為 R-L，所以，以上的過程重復(fù) (R-L)/2 次（向上取整）后，兩者要么相遇，要么發(fā)生錯位。相遇或錯位后，R <= L，新的 R 值便是我們需要的（向下取整的）平均值，即 avg = R-?(R-L)/2?。以上算式全程使用的都是減法，自然不會發(fā)生溢出。

涉及到除法，本關(guān)的攻略還是同樣提供線性查找和二分查找兩種做法。

線性查找

代碼如下：

IN.A 下方的節(jié)點將收到的 a 值匯總到右路（mov up right）。

IN.B 下方的節(jié)點首先接收一個 b 值（mov up acc），再將 b 值復(fù)制一份向下傳遞。接下來需要判斷 a 和 b 誰是 L，誰是 R。這時候自然是令 acc = b - a（sub left）。如果 b - a ≥ 0，那么 b ≥ a，b = R，a = L，我們傳下去的 b 已經(jīng)是 R 了，不需要修正，直接跳到第 7 行（jgz 7）。如果 b - a < 0，那么 b < a，b = L，a = R。那么我們剛才傳下去的 b 其實是 L，需要把它修正為 R 才能開始計算 R-?(R-L)/2? 的值。由于 R = L + (R - L)，而現(xiàn)在 acc = b - a = L - R，所以這里要把 acc 取個反，變成 R - L（neg），再將這個增量值傳下去，令下方將 L 修正為 R（mov acc down）。

接下來就是計算??(R-L)/2? 的值的時候了。此時 acc 正好是 R - L?的值，acc 每減去一次 2，就向下發(fā)送一次 -1 的增量（mov -1 down, sub 2），同時判斷：若 acc 仍是正數(shù)，則跳回第 7 行繼續(xù)減（jgz 7），直到 acc 變?yōu)?0 或負數(shù)為止，向下發(fā)送最終用于修正偏置的 +999（mov 999 down）。綜上所述，我們一共向下發(fā)送了??(R-L)/2? 次 -1，再加上一開始的 R，下方節(jié)點把這么多量累加到一起，得到的自然就是?R-?(R-L)/2? 的值了。

中央節(jié)點純傳話（mov up down）。

右下角的節(jié)點首先將 acc 初始化為偏置值 -999（mov -999 acc），然后會不斷收到中央節(jié)點發(fā)來的商增值，只要沒有發(fā)送 999，商就不會變成正數(shù)，這時只要一直累加就行了（add up, jlz 2）。直到上方突然發(fā)來一個 +999，偏置量 -999 被清除后，我們的商變成了正數(shù)，此時即可將標準答案向下輸出（mov acc down）。

先劇透一下，由于本題的數(shù)字非常大，線性查找算法非常慢，需要 20000+ 的周期才能運行完畢。因此點擊左下角的【FAST】運行程序，點擊【RUN】的話會慢到讓你懷疑人生：

二分查找

我們既可以計算?R-?(R-L)/2? 的值，也可以計算 L+?(R-L)/2? 的值。由于二分除法對向下取整的相性較好，本例里使用向下取整的除法，即計算 L+?(R-L)/2?。

除法部分的商不會超過 500，在 0~511 范圍內(nèi)。由于 0~511 范圍內(nèi)有 512 個可選值，且

所以采用二分查找法時，每次排除掉一半的錯誤選項，最多執(zhí)行 9 步運算即可得出結(jié)論。設(shè)得到的 R - L?的值?為 c，計算步驟如下：

• 檢查 c 是否大于等于 512。若是，則令 c 減去 512，令商加上 256，否則什么都不做；

• 檢查 c 是否大于等于 256。若是，則令 c 減去 256，令商加上 128，否則什么都不做；

• 檢查 c 是否大于等于 128。若是，則令 c 減去 128，令商加上 64，否則什么都不做；

• 檢查 c 是否大于等于 64。若是，則令 c 減去 64，令商加上 32，否則什么都不做；

• 檢查 c 是否大于等于 32。若是，則令 c 減去 32，令商加上 16，否則什么都不做；

• 檢查 c 是否大于等于 16。若是，則令 c 減去 16，令商加上 8，否則什么都不做；

• 檢查 c 是否大于等于 8。若是，則令 c 減去 8，令商加上 4，否則什么都不做；

• 檢查 c 是否大于等于 4。若是，則令 c 減去 4，令商加上 2，否則什么都不做；

• 檢查 c 是否大于等于 2。若是，則令 c 減去 2，令商加上 1，否則什么都不做。

代碼如下：

IN.A 下方的節(jié)點將收到的 a 值向右發(fā)送兩次（mov up acc, mov acc right, mov acc right）。

IN.B 下方的節(jié)點首先計算 b - a 的值（mov up acc, sub left），并將該差值向下發(fā)送一份。接著檢查：如果差值為正，說明 b - a =?R - L，b = R，a = L，我們將代表 L 的 a 再向下發(fā)送一份（jgz 8, mov left down）；如果差值為負，說明 b - a = L - R，b = L，a = R，我們將 acc 加上 a，令 acc = b - a + a = b = L，然后向下發(fā)送（add left, mov acc down, jmp 9）。最后，我們給中央節(jié)點傳 9 個 1 和一個 999（mov 9 acc, mov 1 down, sub 1, jnz b, mov 999 down）。

中央節(jié)點的左右兩側(cè)各加了一個節(jié)點，右邊提供的是用于和 c 比大小的 512~2，左邊提供的是256~1 的商增值。中央節(jié)點首先會收到 b-a 的值（mov up acc），若其為正，說明是?R - L，直接跳到第 4 行（jgz 4）；若其為負，說明是 L - R，將其取反變?yōu)?R - L（neg）。上方緊接著會再傳一個 L 的值，將其直接扔給下方節(jié)點（mov up down）。下方節(jié)點先前已經(jīng)收到了 L 這個增量值，現(xiàn)在正式開始計算 ?(R-L)/2? 的值。

然后，我們就開始聽從上方節(jié)點的命令了（jro up）。上方節(jié)點發(fā)送 1 時，表示需要進行一次運算。設(shè)和 c 比大小的量是 x，本輪的商增量是 y。每從上方節(jié)點收到一次 1 信號，就判斷 c-x 的值（sub right）是否大于等于 0。大于等于 0 時按順序執(zhí)行，小于 0 時跳到第 8 行執(zhí)行（jlz 8）。c-x 大于等于 0 時，本輪的 y 需要累加到商里，因此將 y 值發(fā)給下方，并跳回第 3 行，等待上方節(jié)點的下一次信號（mov left down, jmp 3）。

而當 c-x 小于 0 時，本輪的 y 需要舍棄掉（mov left nil），然后將 c-x 還原成 c。只是我們這次的代碼里并沒有將 c 值存入 bak，該怎么還原呢？

由于下一次的 x 會變成本次 x 的一半，所以收到上方的 1 信號后（jro up），我們需要計算的是 c-x/2 的值。目前 acc 里的值是 c-x 的值，所以此時我們只要加上 x/2（add right），就得到了 c-x+x/2 = c-x/2 的值。得到該值后，若該值小于 0，則跳回到第 8 行執(zhí)行（jlz 8），否則跳回到第 6 行執(zhí)行（jmp 6）。如此，我們便成功地在不使用 bak 的前提下，將 c-x 還原成了 c，并繼續(xù)和接下來的 x/2 比大小。當然了，這種做法只有在計算除數(shù)為 2 的除法時才有效。

當做完了 9?次運算后，你會停留在第 3 行或第 8 行的 jro up 這條指令上，然后你會從上方收到一個 999。這里我要提一條隱藏特性：jro 的偏移量超出了代碼范圍時，會跳轉(zhuǎn)到最近的邊界點。例如，當你從上方收到 999 時，jro up 需要向下跳轉(zhuǎn) 999 行執(zhí)行，但是你的下方?jīng)]有 999 行代碼，所以改為跳到最后一行執(zhí)行。當你從上方收到 -999 時同理，會跳到第一行執(zhí)行。

這里，當 9 次計算執(zhí)行完畢后，我們需要手動給下方發(fā)送一個 999 的偏置修正值，但是此時我們可能停在第 3 行，也可能停在第 8 行，向下的偏移量是不確定的。上方節(jié)點此時只能利用這個隱藏特性，簡單粗暴地傳一個 999，讓中央節(jié)點無腦跳到最后一行執(zhí)行（mov 999 down）。

下方的節(jié)點和上一版方案完全一樣，也是先初始化為 -999 的偏置，然后不斷從上方接收商增值（mov -999 acc, add up, jlz 2），當商突然變成正數(shù)后，下方節(jié)點自然就明白了從上方收到了 999。這時候輸出正確答案即可（mov acc down）。

點擊左下角的【RUN】，稍等片刻，便會彈出結(jié)算界面：

商的范圍擴大了，我們的計算次數(shù)也不得不由 7 次計算增加為 9 次計算，再加上額外的預(yù)處理，所以本次二分算法的運行時長為 2216，相比于上一關(guān)的 660 時長是有所增加的。不過相比于本關(guān)的線性查找，速度快了 10 倍（2216?vs 24515）。