Brainfuck 中的 divmod 算法

Question

有人可以向我解释这段代码吗？我明白它的作用，但我不明白它是如何工作的。

# >n 0 d
[->+>-[>+>>]>[+[-<+>]>+>>]<<<<<<]
# >0 n d-n%d n%d n/d

Answer 1

这是发生的事情：

# >n 0 d

这一行，是一条注释行，告诉您操作前的内存应该是什么样的。股息为n，除数为d。根据代码，接下来的 3 个单元格也应该为空，但在此处被忽略，假设默认情况下为空。

为了更容易理解，我现在以 25/4 为例：

ptr 000 001 002 003 004 005 006
val 025 000 004 000 000 000 000

[->+>-[>+>>]>[+[-<+>]>+>>]<<<<<<]

这条线可以分成几部分以便于观察，但如果你只是使用它，它就是一个神奇的循环：

[->+>-

这部分减去被除数，将其添加回下一个单元格以进行保存，并减去除数。现在的记忆是：

ptr 000 001 002 003 004 005 006
val 024 001 003 000 000 000 000

[>+>>]

这添加了从除数中删除的一个，以便再次保留，因为我们需要它来循环。

ptr 000 001 002 003 004 005 006
val 024 001 003 001 000 000 000

然后，它向右移动 2 步到 cell 005，然后006因为>中间有一个，跳过了[+[-<+>]>+>>]因为单元格是空的，然后因为这一行回到了单元格 000：

<<<<<<

额外的移动很重要，因为为了让系统不再循环，我们需要移动到一个空的空间。移动到006基本上是因为额外的>，这是以后使用所必需的。

让我们跳过一些步骤，继续前进，直到除数变为 0。

ptr 000 001 002 003 004 005 006
val 021 004 000 003 000 000 000

[>+>>]由于单元格 2 现在为空，因此它会跳过，然后移动到单元格003。

[+[-<+>]>+>>]

由于003有一个值，它必须运行这一行。加入一个值，使其成为一个完整的循环，然后移值回002用[-<+>]。指针在 处结束003，因此它移动到004并将该值加一以表示一个完整的循环，从而对商加一。它移动到006并返回到000。

重复整个过程，然后我们得到：

ptr 000 001 002 003 004 005 006
val 000 025 003 001 006 000 000

就像最后一行

# >0 n d-n%d n%d n/d

as 循环终止，因为000现在是空的。n 现在完全移位到001，002并003显示当 n 完全为零时除数的循环过程。004显示除数循环的总完成迭代。