algorithm - 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 步到单元格 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显示除数循环的总迭代次数。