【TIS-100 攻略】TIS-NET 第 7 关：信号均值计算器
本文首发于 B 站《TIS-100》文集（https://www.bilibili.com/read/readlist/rl626023）。原创不易，转载请注明出处。
TIS-NET 第 7 关《信号均值计算器》（Signal Averager）关卡展示
本关需要将 IN.A 和 IN.B 的均值，即 (a+b)/2 的值，发送给 OUT。当均值出现了小数时，向下取整，而不是四舍五入。
这里我们首先要解决的是【a+b 超过三位数怎么办】的问题。TIS-100 里，每个节点的 acc 和 bak 里的数字都必须在 -999~999 的范围内，如果在计算的过程中发生了数值溢出，则结果会被自动替换为最近的边界值。
所以，假如你从 IN.A 里收到了 777，从 IN.B 里收到了 888，然后你直接将两者相加的话，acc 会变成 999 而不是期望的 1665。你在错误的中间结果上做除以 2 的运算，得到的最终结果也一定是错误的。一步错，步步错。
那么我们该怎么在不触发溢出的前提下，正确得到 a+b 的值呢？这里我们要脱离思维定式，a 和 b 的平均值就非得用 (a+b)/2 来计算吗？这里，我们设两者中的较小值为 L，较大值为 R。那么求平均值的过程，就是 L 和 R 两者不断靠近的过程。L 每加上 1，R 就减去 1，直到两者相遇或发生错位为止。两者每执行一次上述动作，两者间的距离就减少 2。因为两者的初始距离为 R-L，所以，以上的过程重复 (R-L)/2 次（向上取整）后，两者要么相遇，要么发生错位。相遇或错位后，R <= L，新的 R 值便是我们需要的（向下取整的）平均值，即 avg = R-⌈(R-L)/2⌉。以上算式全程使用的都是减法，自然不会发生溢出。
涉及到除法，本关的攻略还是同样提供线性查找和二分查找两种做法。
线性查找
代码如下：
IN.A 下方的节点将收到的 a 值汇总到右路（mov up right）。
IN.B 下方的节点首先接收一个 b 值（mov up acc），再将 b 值复制一份向下传递。接下来需要判断 a 和 b 谁是 L，谁是 R。这时候自然是令 acc = b - a（sub left）。如果 b - a ≥ 0，那么 b ≥ a，b = R，a = L，我们传下去的 b 已经是 R 了，不需要修正，直接跳到第 7 行（jgz 7）。如果 b - a < 0，那么 b < a，b = L，a = R。那么我们刚才传下去的 b 其实是 L，需要把它修正为 R 才能开始计算 R-⌈(R-L)/2⌉ 的值。由于 R = L + (R - L)，而现在 acc = b - a = L - R，所以这里要把 acc 取个反，变成 R - L（neg），再将这个增量值传下去，令下方将 L 修正为 R（mov acc down）。
接下来就是计算 ⌈(R-L)/2⌉ 的值的时候了。此时 acc 正好是 R - L 的值，acc 每减去一次 2，就向下发送一次 -1 的增量（mov -1 down, sub 2），同时判断：若 acc 仍是正数，则跳回第 7 行继续减（jgz 7），直到 acc 变为 0 或负数为止，向下发送最终用于修正偏置的 +999（mov 999 down）。综上所述，我们一共向下发送了 ⌈(R-L)/2⌉ 次 -1，再加上一开始的 R，下方节点把这么多量累加到一起，得到的自然就是 R-⌈(R-L)/2⌉ 的值了。
中央节点纯传话（mov up down）。
右下角的节点首先将 acc 初始化为偏置值 -999（mov -999 acc），然后会不断收到中央节点发来的商增值，只要没有发送 999，商就不会变成正数，这时只要一直累加就行了（add up, jlz 2）。直到上方突然发来一个 +999，偏置量 -999 被清除后，我们的商变成了正数，此时即可将标准答案向下输出（mov acc down）。
先剧透一下，由于本题的数字非常大，线性查找算法非常慢，需要 20000+ 的周期才能运行完毕。因此点击左下角的【FAST】运行程序，点击【RUN】的话会慢到让你怀疑人生：
二分查找
我们既可以计算 R-⌈(R-L)/2⌉ 的值，也可以计算 L+⌊(R-L)/2⌋ 的值。由于二分除法对向下取整的相性较好，本例里使用向下取整的除法，即计算 L+⌊(R-L)/2⌋。
除法部分的商不会超过 500，在 0~511 范围内。由于 0~511 范围内有 512 个可选值，且
所以采用二分查找法时，每次排除掉一半的错误选项，最多执行 9 步运算即可得出结论。设得到的 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 下方的节点将收到的 a 值向右发送两次（mov up acc, mov acc right, mov acc right）。
IN.B 下方的节点首先计算 b - a 的值（mov up acc, sub left），并将该差值向下发送一份。接着检查：如果差值为正，说明 b - a = R - L，b = R，a = L，我们将代表 L 的 a 再向下发送一份（jgz 8, mov left down）；如果差值为负，说明 b - a = L - R，b = L，a = R，我们将 acc 加上 a，令 acc = b - a + a = b = L，然后向下发送（add left, mov acc down, jmp 9）。最后，我们给中央节点传 9 个 1 和一个 999（mov 9 acc, mov 1 down, sub 1, jnz b, mov 999 down）。
中央节点的左右两侧各加了一个节点，右边提供的是用于和 c 比大小的 512~2，左边提供的是256~1 的商增值。中央节点首先会收到 b-a 的值（mov up acc），若其为正，说明是 R - L，直接跳到第 4 行（jgz 4）；若其为负，说明是 L - R，将其取反变为 R - L（neg）。上方紧接着会再传一个 L 的值，将其直接扔给下方节点（mov up down）。下方节点先前已经收到了 L 这个增量值，现在正式开始计算 ⌊(R-L)/2⌋ 的值。
然后，我们就开始听从上方节点的命令了（jro up）。上方节点发送 1 时，表示需要进行一次运算。设和 c 比大小的量是 x，本轮的商增量是 y。每从上方节点收到一次 1 信号，就判断 c-x 的值（sub right）是否大于等于 0。大于等于 0 时按顺序执行，小于 0 时跳到第 8 行执行（jlz 8）。c-x 大于等于 0 时，本轮的 y 需要累加到商里，因此将 y 值发给下方，并跳回第 3 行，等待上方节点的下一次信号（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 行执行（jlz 8），否则跳回到第 6 行执行（jmp 6）。如此，我们便成功地在不使用 bak 的前提下，将 c-x 还原成了 c，并继续和接下来的 x/2 比大小。当然了，这种做法只有在计算除数为 2 的除法时才有效。
当做完了 9 次运算后，你会停留在第 3 行或第 8 行的 jro up 这条指令上，然后你会从上方收到一个 999。这里我要提一条隐藏特性：jro 的偏移量超出了代码范围时，会跳转到最近的边界点。例如，当你从上方收到 999 时，jro up 需要向下跳转 999 行执行，但是你的下方没有 999 行代码，所以改为跳到最后一行执行。当你从上方收到 -999 时同理，会跳到第一行执行。
这里，当 9 次计算执行完毕后，我们需要手动给下方发送一个 999 的偏置修正值，但是此时我们可能停在第 3 行，也可能停在第 8 行，向下的偏移量是不确定的。上方节点此时只能利用这个隐藏特性，简单粗暴地传一个 999，让中央节点无脑跳到最后一行执行（mov 999 down）。
下方的节点和上一版方案完全一样，也是先初始化为 -999 的偏置，然后不断从上方接收商增值（mov -999 acc, add up, jlz 2），当商突然变成正数后，下方节点自然就明白了从上方收到了 999。这时候输出正确答案即可（mov acc down）。
点击左下角的【RUN】，稍等片刻，便会弹出结算界面：
商的范围扩大了，我们的计算次数也不得不由 7 次计算增加为 9 次计算，再加上额外的预处理，所以本次二分算法的运行时长为 2216，相比于上一关的 660 时长是有所增加的。不过相比于本关的线性查找，速度快了 10 倍（2216 vs 24515）。
