4

我试图理解为什么双重涉猎算法有效，但我不明白。

对算法的步骤和目的有很多很好的描述，例如 http://www.classiccmp.org/cpmarchives/cpm/mirrors/cbfalconer.home.att.net/download/dubldabl.txt或 http: //en.wikipedia.org/wiki/Double_dabble

也有一些解释的尝试。我找到的最好的是这个：http: //www.minecraftforum.net/forums/minecraft-discussion/redstone-discussion-and/340153-why-does-the-double-dabble-algorithm-work#c6

但我仍然觉得我缺少连接部分。这是我得到的：

  • 我明白了，您可以通过从左到右读取二进制数将它们转换为十进制数，从十进制值 0 开始，遍历二进制数的数字，每达到 1 就将十进制数加 1二进制数，并乘以 2，当您移动到下一个数字时（如最后一个链接中所述）。
    • 但是为什么这会导致双涉算法呢？我们不想转换成十进制，我们想转换成 BCD。为什么我们保留乘法（移位），但我们放弃加 1？连接在哪里？
  • 我明白了，当 BCD 字段中的数字在移位前超过 4 时，为什么我们必须加 3。因为如果您希望 BCD 数在移位时乘以 2，则必须进行一些修正。如果您移动 BCD 数字0000 1000(8) 并且想要获得双0001 0011(16)，则必须在移动前添加 3（6 的一半），因为只需移动，您最终会得到0001 0000(10)（您错过了6）。
    • 但是为什么我们想要这个，加 1 发生在哪里呢？

我想我只是缺少了一小部分。

4

4 回答 4

1

将 N 转换为其十进制表示需要在除以 10 后重复确定 R（剩余）。除了除以 10，您还可以除以 2（这只是一个移位），然后除以 5。因此是 5。长除法意味着尝试减去 5，如果成功，则实际执行减法，同时通过在 Q 中设置一个位来跟踪该成功。添加 3 与在设置随后将移入 Q 的位时减去 5 相同。因此是 3。

于 2018-02-09T15:37:04.603 回答
1

二进制中的 16 是 bcd 中的 10。我们想要 bcd 中的 16，所以我们添加 6。但是为什么我们添加 3 而不是 6？

因为加法是在移位之前完成的，所以都是除以2，这就是为什么我们在大于5的时候加3！

于 2018-10-10T00:46:48.313 回答
0

我想我在写这个问题时得到了它：假设你想1111 1111从二进制转换为 BCD。

我们使用该方法将二进制数转换为十进制数，在问题中进行了解释，但我们对其进行了一些更改。

我们不是从十进制数 0 开始，而是从 BCD 数0000 0000(0) 开始。

BCD binary

0000 0000 1111 1111

首先，我们必须将 BCD 数加 1。这可以通过一个简单的转变来完成

0000 0001 1111 1110

现在我们继续，想要将 BCD-Number 乘以 2。在下一步中，我们要将当前二进制数字添加到 BCD-number。两者都可以通过（再次）转移一步完成。

0000 0011 1111 1100

这一遍又一遍地起作用。唯一不起作用的情况是 BCD 数的块超过 4。在这种情况下，您必须执行问题中解释的修复。

遍历二进制数后，您会得到左侧数字的 BCD 表示 \o/

于 2015-02-23T09:44:21.180 回答
0

整个想法是使用链接中解释的移位，然后将左侧的数字转换为 BCD。在每个阶段，您都越来越接近左边的实际二进制数，但要确保该数字保持为 BCD 而不是二进制。

当您移入“1”时，您实际上是在添加它。

查看下面的链接以了解“添加 3”参数的要点：

https://olduino.files.wordpress.com/2015/03/why-does-double-dabble-work.pdf

于 2015-06-13T09:09:49.603 回答