问不使用除法运算符的未知分母优化除法

EN

这里有一个想法，它使用一个乘法和一个移位，所以在大多数系统中它会比除法更快。由于您的分子最多为768,000,000 ~= 30位，所以我们在32位字中没有太多空间，所以我们必须使用64位乘法。

主要思想是利用以下事实：

x / y == (x * k) / (y * k)

除以2的幂是一种简单、快速的位移位。

因此，为了选择一个特定的示例，假设x = 700,000,000和y = 47 (因此正确的商数是14,893,617)。为了避免舍入误差，我们的移位需要大约是我们可能的最大分子的大小- 30位。找到与y * k = 2^30最接近的k的值，在本例中为k = 22845571。然后是x * k = 0x38D08C4CE6F500。将其移位30位得到0xE34231 = 14,893,617，这是我们的期望商。出于舍入的目的，您可能需要为分子/分母的某些组合添加1-2位，除非在商中减去1是可以接受的。

然后，练习变成为每个可能的分母创建一个具有正确乘数的查找表。

编辑:正如下面的评论所指出的，选择k = (2^30 + y - 1) / y应该比简单的k = round(2^30 / y)提供更好和更一致的结果。

大@ss表适用于较小的数字：

unsigned int divTable[kMaxNumerator][64] = {...}

你把每个可能除法的值放在那里。在特定大小以上不是很实用，但它确实适用于包含的情况，并且在很久以前是纹理贴图的常见解决方案:)然后我读了你的评论，看到你在768,000,000范围内，这是因为除非你能处理相当多的精度损失，否则这是完全不切实际的。