brainfuck中的divmod算法

Divmod algorithm in brainfuck

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

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

事情是这样的:

# >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:

<<<<<<

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

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

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

它跳过 [>+>>] 因为单元格 2 现在是空的,然后它移动到单元格 003

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

既然003有值,就得运行这一行。将值加一使其成为一个完整的循环,然后使用 [-<+>] 将值移回 002。指针在 003 处结束,因此它移动到 004 并将该值加 1 以指示一个完整的循环,从而将商加一。它移动到 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现在完全移到001002003表示n完全归零时除数的循环过程。 004 显示除数循环的总迭代次数。