【TIS-100 攻略】第 19 关：除法器
本文首发于 B 站《TIS-100》文集（https://www.bilibili.com/read/readlist/rl626023）。原创不易，转载请注明出处。
第 19 关《除法器》（Signal Divier）关卡展示
本关要求向 OUT.Q 口输出 IN.A 除以 IN.B 的商，向 OUT.R 口输出 IN.A 除以 IN.B 的余数。
我们首先想到的是用减法来模拟除法：当被除数 >= 除数时，令被除数减去除数，同时商 +1。直到不够减时，输出得到的商，同时被除数剩下不够减的值就是余数。代码如下：
上方的两个节点和中央的两个节点都是往下传话的（mov up down），重头戏全部在下边两个节点里。
左下角的节点得到的是 A（被除数），需要计算 Q（商）；右下角的节点得到的是 B（除数），需要计算 R（余数）。我们先看右下角节点的逻辑：
由于被除数减去除数的次数和最终的商相关，所以右下角的节点自己是不知道需要提供多少次除数的，它需要由左下角的节点告诉它是继续提供除数，还是开始计算余数。右下角的节点收到除数 B 后（mov up acc），
给左边发一份（mov acc left），
接下来听从左边的指令（jro left）：如果左边发送了 -1，就说明被除数没减到负数，我要回到上一行，继续给左边提供除数；
而如果左边发送了 1，就说明已经确定好了商，这时候我要跳到下一行，加上左边发来的值（add left）得到余数（为什么这样做能得到余数，后续有补充）。
将得到的余数发送到下方的 OUT.R 端口（mov acc down）。
右下角节点的行动依赖左下角节点的指令，我们再来看左下角节点的逻辑：
左下角的节点收到被除数 A 后（mov up acc），
减去右边发来的除数（sub right），然后判定除数是否减到了负数。
若减到了负数，则跳到第 9 行（jlz 9），否则按顺序执行。
尚未减到负数时，给右边发送 -1 信号，告诉右边节点：下回合我还要继续减你这个除数（mov -1 right）。
发送完 -1 信号后，将记录商的 bak 寄存器加上 1（swp）
（add 1）
（swp）
然后跳回到第 2 行接着减（jmp 2）。
直到被除数减到负数后，我们跳到第 9 行。首先给右边节点发送 1，通知右边节点接收我这个减到了负数的被除数（mov 1 right），
通知完毕后，发送该负数（mov acc right）
并清零（sub acc），
紧接着把 bak 里的商（swp）
发送到下方的 OUT.Q 端口（mov acc down）。
右下角节点在左边的被除数减到负数前，都是一直给左边发送除数的。当被除数减到了负数时，说明减过了，此时需要加回一个除数才能得到正确的余数。右下角节点里的 acc 存着的正是除数，所以此时我们接收左边发来的负数，加到这个除数上（add left），就得到了余数。
点击左下角的【RUN】，稍等片刻，便会弹出结算界面：
使用【二分查找法】加快运行速度
以上算法，我们相当于在一步一步试商：
检查商能否增加 1，即被除数是否大于等于除数。若能，则令被除数减去除数，同时商 +1；
接着，继续检查商能否增加 1，即被除数是否大于等于除数。若能，则令被除数减去除数，同时商 +1；
……
如此反复，直到某一刻商不能增加 1 为止。
但其实我们不是非得这样一点一点试商的。我们完全可以一步迈大一点，然后根据反馈结果，决定继续向前迈进，还是往后撤退。考虑到本题的被除数和除数都不会超过两位数，所以商撑死了也只有 99。我们可以把算法改进成下面这个样子：
检查商能否增加 64，即被除数是否大于等于 64×除数。若能，则令被除数减去 64×除数，同时商 +64；若不能，则本步什么都不做。
检查商能否增加 32，即被除数是否大于等于 32×除数。若能，则令被除数减去 32×除数，同时商 +32；若不能，则本步什么都不做。
检查商能否增加 16，即被除数是否大于等于 16×除数。若能，则令被除数减去 16×除数，同时商 +16；若不能，则本步什么都不做。
检查商能否增加 8，即被除数是否大于等于 8×除数。若能，则令被除数减去 8×除数，同时商 +8；若不能，则本步什么都不做。
检查商能否增加 4，即被除数是否大于等于 4×除数。若能，则令被除数减去 4×除数，同时商 +4；若不能，则本步什么都不做。
检查商能否增加 2，即被除数是否大于等于 2×除数。若能，则令被除数减去 2×除数，同时商 +2；若不能，则本步什么都不做。
检查商能否增加 1，即被除数是否大于等于 1×除数。若能，则令被除数减去除数，同时商 +1；若不能，则本步什么都不做。
输出算好的商，同时被除数减剩下的值即为余数。
以上做法相当于每一步都将商的取值范围缩小一半。当商的取值范围在 0~127 内时，首先我们检查被除数是否大于等于 64×除数，若满足条件，则商至少为 64，我们就把商的范围限定在了 64~127 这部分；若不满足条件，则 64 这个商就大了，我们就把商的范围限定在了 0~63 这部分。
后面的每一步，都是跟第一步一样，选择新的取值范围内的中心点来试商，并根据反馈结果继续缩小取值范围，直到最终取值范围落到一个点上。
0~127 这个取值范围，每次缩小一半，缩小 7 次后，取值范围就变成了唯一的一个点。因此，我们采用以上算法后，不论被除数和除数的值为多少，我们都可以通过 7 次计算得到商和余数。综合效率比原先的一个一个慢慢试要高多了。
像这样子的先确定取值范围，然后每次用范围内的中心点来试错，并根据反馈每次将查找范围缩小一半的算法，就叫【二分查找法】。我之所以假设商的范围是在 0~127 之间，而不是跟题目一样的 0~99 之间，是因为 0~127 这个取值范围能被完美地二等分 7 次，而 0~99 不行，第三次分割（0~24、25~49、50~74、75~99）时，长度就是奇数了，就没法二等分了，这样反而会增加算法的复杂度。
二分查找法的计算效率和取值范围呈对数相关。传统的那种一个一个尝试的算法叫【线性查找】，最坏情况下要把取值范围内的所有数字都尝试一遍，才能得出结论。而本次的二分查找算法，由于每计算一次都会排除掉【一半】的错误选项，所以实际的计算次数跟取值范围可以被二等分的次数一致。比如 0~127，总共有 128 个数，能被 7 次二等分，即二等分的次数是
本题若使用二分查找算法，无论最好情况还是最坏情况，通通计算 7 次得出结论，相比之下线性查找最好情况计算 1 次，最坏情况计算 128 次才能得出结论。虽然线性查找偶有胜出的时刻，但综合来看，本题用二分查找算法，运算速度远优于线性查找算法。
本题采用【二分查找法】的代码如下：
IN.A 下方的节点没啥好说的，把收到的被除数往右传（mov up right）。接下来是 IN.B 下方的节点：
IN.B 下方的节点收到除数后，将它发给右上角的节点（mov up right）。右上角的节点在收到除数后，通过 add acc 指令，不断将 acc 扩大两倍，依次得到 1 倍除数（mov left acc, mov acc down）、2 倍除数（add acc, mov acc down）、4 倍除数（add acc, mov acc down）、8 倍除数（add acc, mov acc down）、16 倍除数（add acc, mov acc down）、32 倍除数（add acc, mov acc down）以及 64 倍除数的值（add acc, mov acc left）。除最后一个数发给左边，不放入栈中外，其余数字都放入栈中。
接下来，IN.B 下方的节点把从左边收到的被除数传给下面的节点（mov left down），等待右上角的节点将 1~32 倍除数都放入栈中，最后将 64 倍除数发来后，
将这个 64 倍除数传给下面的节点（mov right down）。为什么不把这 7 个数全部放栈里，偏偏要把最后的 64 倍除数发过来呢？这是为了信号同步的需要，只有把 1~64 倍的除数全部准备好后，才能开始计算。而我们并不知道右上角节点什么时候把这些数字全部准备好。右上角节点将最后的 64 倍除数发过来的同时，我们也就知道了，所有的数都准备好了，可以开始工作了。
这个节点在把 64 倍除数发下去后，同样也会等待下方节点发一个数上来（mov down acc）。我们只是将这个数存入 acc，却不去读它。原因也在于这也是一个同步信号，我们需要等下方节点计算完毕后才能开始做下一次任务。那么我们怎么知道下方节点什么时候计算完毕呢？答案是等待下方发一个数字上来。发的数字是什么不重要，只要你跟我打了这声招呼就行了，我就可以开始干下一份活了。
然后我们来看中央靠右的节点：
首先它会从上面收到本轮的被除数和 64 倍除数，将它们通通发往右下角的节点（mov up down）
（mov up down）
之后由于栈中还有 32~1 倍的除数，共 6 个数字，该节点需要将这 6 个数字全部取出。首先将 acc 计数器置为 6（mov 6 acc），
然后每取出一个数字，就给下方发送一个 -7 信号和这个数字（mov -7 down）
和这个数字（mov right down）
并令计数器减去 1（sub 1）。
只要计数器尚未减到 0，就跳回第 4 行继续发送（jnz 4），
直到计数器变为 0，将栈取空后，给上方随便发送一个数字，让上方开始准备下一份活（mov 0 up），
同时再给下方发一个 1 信号（mov 1 down）。
现在来看右下角的节点：
首先它会从上方收到被除数和 64 倍除数，将被除数复制一份到 bak 中，以便被除数不够减时能够从 bak 还原（mov up acc）
（sav）
然后和 64 倍除数做差（sub up）。
若差值为负数，则跳到第 7 行执行（jlz 7）。以下代码中，第 5~6 行是未到达负数时的操作，第 7~8 行是到达了负数时的操作。
被除数尚未到达负数时，说明本轮是够减的，我们要发送一个 1 信号给左边的节点，令左边节点将商加上 64（mov 1 left），
接着直接跳到第 9 行的 jro 指令处，跳过第 7~8 行的互斥逻辑（jmp 9）。
如果本轮的被除数到达了负数，说明本轮是不够减的，我们要发送一个 3 信号给左边的节点（mov 3 left），告诉左边节点，丢弃掉本次的增量值。
然后我们还要把 bak 里的原被除数还原回来，丢弃掉当前这个已经减到负数的被除数（swp）。
做完这些后，我们开始听从上方发来的后续指令（jro up）。上方还剩 32 倍、16 倍、8 倍、4 倍、2 倍、1 倍除数没有发。上方在发这些数之前，会先发送一个 -7，我们向上跳 7 行，跳到上面的 sav, sub up 处，继续将被除数和剩下的 32 倍、16 倍、8 倍、4 倍、2 倍、1 倍除数比大小，并通知左边的节点为商加上或丢弃掉 32、16、8、4、2、1 的增量值。
而上方将栈里的数字掏空后，会给我们发一个 1 信号，此时我们先给左边发送一个 5 信号（mov 5 left），让左边将算好的商向下方的 OUT.Q 发，
然后自己把得到的余数往自己的下方的 OUT.R 发（mov acc down）。
左下角的节点是用来算商的：
中央靠左的辅助节点早就准备好为它传递 64、32、16、8、4、2、1 这几个商的增量值了（mov 64 down, mov 32 down, mov 16 down, mov 8 down, mov 4 down, mov 2 down, mov 1 down）。它会不断听从右边计算余数的节点的指令（jro right）。
当右边发来 1 时，本轮的被除数是够减的，我们需要向下跳 1 行从上方读出本轮的增量值，加到商里（add up）
（jmp 1）
当右边发来 3 时，本轮的被除数是不够减的，我们需要向下跳 3 行，将本轮的增量值丢弃（mov up nil）
（jmp 1）
当右边发来 5 时，说明 7 次计算都已执行完毕，我们需要向下跳 5 行，将得到的商发送给下方的节点（mov acc down），
并清空本次的计算结果，准备迎接下一次计算（sub acc）。
点击左下角的【RUN】，稍等片刻，便会弹出结算界面：
将线性查找算法改为二分查找算法后，运行时长由 7105 周期骤降到 2737 周期，速度提升了将近 3 倍。当然代码行数和用到的节点数也相应地增加了，本算法属于土豪才能玩得起的算法。
