algorithm - 是否可以设计一种不首先比较输入的减法算法？

Question

显然，任何称职的编程语言都有内置的减法。但是，假设您需要实现自定义减法算法(例如，处理非常大的数字)。如果您使用借用方法，则必须首先比较输入以确定结果是否为负，如果是，则切换减法的顺序。我很好奇是否可以编写不需要这种比较/操作数交换的算法？

此外，这样的算法是否比比较优先更有效，后者在最坏的情况下必须比较每个位值？

*我知道可以使用补码，但这限制了允许输入的大小(假设表示大小有限)。

Answer 1

如果你正在实现 bignums，那么你可以结合比较和减法，这样你就只看每个 "limb"一次，除了一个。 (“肢体”一词来自 Gnu MP 库，但它在其他地方也用于表示同一事物。)

首先，您从较长数字的大端开始扫描，直到找到非零肢或到达较小数字的长度。在第一种情况下，你知道越长的数字越大，你也知道它最重要的肢体的位置。 (如果您采用数字始终具有非零最重要分支的惯例，那么您可以跳过此步骤。)

现在假设你没有证明越长的数越大，所以你知道两个数在相同的位置。继续扫描这两个数字，直到发现不同为止。此时，您知道哪个数字更大，并且您也知道较大数字的最重要肢体的位置。

所以现在您知道哪个数字更大，您可以从数字的低位端执行正常的借用算法，当您到达您之前确定的高位分支时停止。

由于两次扫描在同一个位置停止，您不会多次查看任何肢体，排除停止第一次扫描的高阶肢体。

---

是否真的值得实现此 hack 是您必须决定的事情。并发症可能不合理。但这是可能的。