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

显示除数循环的总迭代次数。

Answer 2

请小心该算法，因为它无法处理除以 1 的情况，并且在尝试这样做时会弄乱内存。

我没有足够的声誉来发表评论，所以我将其写为答案。