Double Dabble算法笔记
本地笔记整理，原文写于2019/7/8，2019/12/8上传
Double Dabble算法是二进制转BCD的常用算法。
整数Double Dabble算法
（下文当中，"BCD位"指一个十进制位对应的四位二进制）
首先，如果我们要计算一个二进制数的十进制值，除了位权展开以外，可以从左往右如此迭代：
在Double Dabble的图示当中，左边一列存储的是BCD的结果：
Double
Dabble算法本身其实就是在这BCD的结果列进行如上的迭代操作（乘加位）。
为了这样做，直觉上来讲，我们可以按照二进制的方法将BCD列中的结果乘（左移），然后进行一定的矫正（之前的左移可能破坏了BCD的性质），然后在加上原数的一个二进制位（最右边移进）。
左移是平凡的，加上一位也是平凡的（因为左移之后最右边一位永远是，不会产生进位），问题在乘
后为了维护BCD性质所进行的矫正上。
首先，我们应该注意到，忽略进位，如果一个BCD位大于，我们需要减
来获得正确的位，而减
在四位二进制意义下就等同于加
，即
。
Double
Double算法的首先高在它甚至在乘之前就进行了矫正。我们考虑哪些BCD位乘
之后会出现问题，答案非常平凡：满
的。而因为是在左移之前，加上的
也就变成
，即加
。
这就是“满五加三”的由来。
不仅如此，Double
Dabble算法高在因为这是对于左移之前的四位进行的操作，因而加之后会进位到四位当中的最高位，其左移之后就到左边的BCD位上去了...相当于巧妙handle进位的问题。
小数Double Dabble算法
小数Double Dabble似乎没多少人提到……但是本质确实是和整数算法一致的。
我们进行小数二进制-十进制转化可以利用如下的从右往左的迭代过程：
首先是的部分，由于结果列现在表示小数部分，加上去的二进制列就在整个结果列的左侧（整数部分），这无疑是平凡的。
接下来是除的部分。基于二进制的思想，我们通过右移来完成除
的操作。同时我们需要进行一定的矫正来维护BCD的性质。
我们观察到，出现问题的BCD位，一定是在右移之前是奇数的位，而奇数最低位上的，在右移之后，就到了右边的最高位上，也就是右边的哪一位右移之后会大于等于
。
而回到十进制，如果一个奇数位除以二，结果应该给右边的位加上，而我们之前算法中右移过来的
让它加了
，所以要减去
。
这就是“满八减三”的由来。