第一的

不幸的是，我们似乎没有在这个 stackexchange 中打开 MathJax，所以下面的数学部分格式非常糟糕。我也离数学家很远，所以符号可能在某些地方是错误的。

理解幻数和代码

上面代码的目标是将除法重写为乘法，因为除法比乘法需要更多的时钟周期。它大约是周期数的两倍，这在很大程度上取决于 CPU。所以我们需要找到一种很好的无分支方式来做到这一点。如果我们分支，我们很可能会输给简单的除法。

一种方法是简单地意识到除法与乘以数字的倒数相同，即。问题是将其存储为整数是一个非常糟糕的数字。所以我们需要将除数和被除数都乘以某个数。由于我们对 32 位数字进行运算并且我们得到 64 位数字的乘法结果，因此我们获得了最佳精度，并且还避免了溢出问题。所以我们基本上得到了。现在小数部分是导致我们出现问题的原因，因为它会导致舍入错误。

因此，让我们尝试将其正式化：

我们的被乘数在哪里，例如，或者实际上是任何数字，但与我们的寄存器大小配合得很好，因为我们可以简单地丢弃较低的 32 位寄存器。是您必须添加的数字才能被 整除。是我们希望除以的数字。

我们可以将上面的等式改写为

这说明了我们将被除数除以除数，然后是 的误差因子这一点。

研究我们的原始方程很明显我们可以影响很小。需要是 2 的幂，不能太大，否则我们有溢出的风险，不能太小，因为它对我们的错误因子有直接的负面影响。直接取决于和。

所以让我们试试它给出了一个最大误差部分用的最大值是，那么，不幸的是这不小于所以我们可以得到舍入误差。

我们将增加to的指数，从而得到小于 的最大误差分数。这意味着我们的被乘数不小于或等于我们可以存储在 32 位寄存器 ( ) 中的最大有符号值。所以我们改为制作被乘数。作为一个侧面说明，由于补的魔法时，我们减去数是这是当解释为一个无符号数。但我们在这里做有符号算术。所以我们需要通过添加. 这也只解决了 的问题，对于负数，我们将减去 1，因此如果我们有负数，我们需要加 1。

这就是乘法中常数的解释以及如何得出它。现在让我们看一下代码：

; Load -1840700269
mov    ecx,0x92492493

; Load n
mov    eax,edi

; n * -1840700269
imul   ecx

; add n to compensate for 2^32 subtraction
add    edx,edi

; check the sign bit of our result
mov    ecx,edx
shr    ecx,0x1f

; divide by 2^2 to compensate for us using y=2^34 instead of 2^32
sar    edx,0x2

mov    eax,edx
; add the value of the sign bit to the final result
add    eax,ecx

从幻数和代码计算除数

我还没有在数学上证明这一点，但是如果你想从你展示的汇编转储中恢复除数，我们可以做一些简单的心理练习。首先我们需要认识到以下成立

我们为了将值带入 32 位值范围而进行的调整在哪里。从我们可以设计以下代码，右移两次意味着我们有, , ,是未知的。这意味着我们缺少一个变量来执行完美的解决方案。然而，如果可以忽略不计，其目的是使除数尽可能接近其整数值。这意味着可以通过求解来找到解

另一个例子是除数 31337，它的被乘数幻数是 140346763，右移 10 位。

最后

有关其工作原理的完整数学分解，包括用于计算幻数、移位和加法的所有适当证明和算法，请参阅Hacker's Delight，第 10-3 章。

这是一个迟到的回应。所述REKO反编译器通过执行使用分而治之搜索恢复整数除数mediants。

Reko 首先识别使用 64 位乘积 ( r * c)的高位字的模式。常数乘数c除以 2^32 以产生一个介于 0.0 和 1.0 之间的双精度浮点数。从有理数 0 / 0 和 1 / 1 开始，Reko 计算包含浮点数的中位数序列。它从这个中位数序列中选择最接近浮点数的有理数并返回它。

该代码尚未完全测试 - 我还没有机会使用负数，例如，但似乎给出了合理的结果。如果你好奇，代码在这里：https : //github.com/uxmal/reko/blob/master/src/Decompiler/Analysis/ConstDivisionImplementedByMultiplication.cs

这篇论文可能很有趣：Division by invariant multiplication。

在这里撞到了。