爲什麼double-dabble算法有效？

Question

我想了解爲什麼double-dabble算法正在工作，但我沒有得到它。

有很多的步驟，偉大的描述和算法的目的，類似 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，當轉到下一個數字時（如上一個鏈接所述）。
  • 但是，爲什麼這會導致double-dabble算法？我們不想用十進制進行轉換，我們想要以BCD進行轉換。爲什麼我們保持乘法（移位），但是我們放棄了1的加法？連接在哪裏？
• 我得到了，爲什麼我們必須添加3，當BCD字段中的數字在移位之前超過4。因爲如果你想讓BCD碼乘以2，如果你移動它，你必須做一些修正。如果您將BCD編號0000 1000（8）並且您想要得到雙重0001 0011（16），您必須在轉移之前添加3（6的一半），因爲通過轉移您最終以0001 0000（10）（您'失蹤6）。
  • 但是，爲什麼我們想要這個和發生1的加法在哪裏？

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

Answer 1

我想我在寫這個問題時得到了它： 假設你想把1111 1111從二進制轉換成BCD。

我們使用該方法將二進制數轉換爲十進制數，在問題中進行了解釋，但我們稍微改變了它。

我們不是以0的十進制數字開頭，但BCD數字爲0000 0000（0）。

BCD binary

0000 0000 1111 1111

首先我們要1添加到BCD-數。這可以通過一個簡單的移位

0000 0001 1111 1110

現在我們繼續前進，希望通過2乘以BCD-數在我們希望目前的二進制數字添加到BCD-號的下一個步驟來完成。兩者都可以通過（再次）移動一步完成。

0000 0011 1111 1100

這工作了一遍又一遍。唯一的情況是這種情況不起作用，那就是當一個BCD-numer塊超過4個時。在這種情況下，你必須在問題中進行解釋。

通過二進制數迭代之後，你得到的數字的BCD-表示左側\ O/

Answer 2

的整體思路是利用移動在您的鏈接解釋，但隨後就轉換爲數字左轉BCD。在每個階段，您都會接近左邊的實際二進制數字，但要確保數字保持BCD而不是二進制。

當你在'1'中移動時，你基本上是在添加它。

看看下面的鏈接來獲得「添加3」爭論的要點：

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

Answer 3

轉換N到其十進制表示由10分割後涉及反覆地確定R（其餘部分）。除了10分之外，你也可以除以2（這只是一個移位），然後除以5.因此，5.長分裂意味着試圖減去5，如果在保持跟蹤的同時實際上做了減法通過在Q中設置一位來實現成功。加上3與設置隨後將被移入Q的位相減5相同。因此，3.