C语言中的定点无符号除法

Question

我需要一个算法，在C语言中可以做无符号定点除法。我最多可以使用32位字。希望能最小化整数部分所需的位数，并能够使用范围在[0..15]内的数字。显然，最小位数为4位。问题是，我提出的算法只适用于5位。因为它将余数与除数进行比较，然后将余数移位直到大于除数，如果除数的最高位为1，则算法将仅对余数进行移位（它永远不会变得更大）。以下是代码：

int divu(int a, int b){
   int pt_int, r, pt_frac=0;
   int i;

   pt_int = ((unsigned) a/b) << BITS_FRAC;
   r = (unsigned) a%b;

   for (i=BITS_FRAC; i>=0; i--){
      if ((unsigned) r < b)
         r <<= 1;
      else{
         r -= b;
        pt_frac += 01 << i;
        r <<= 1;
      }
   }
   return pt_int + pt_frac;
}

如果你已经有解决方案，但不想了解代码，请直接发布它。 :)

例如：

我们想把1.5除以2，结果为0.75。假设我们使用4位整数部分和28位小数部分。所以我们的数字是十六进制的：

1.5:    0x18000000
2:      0x20000000
result: 0x0c000000 

- Kei Nivky

---

我不理解这个问题。你能提供一个示例输入，以及预期和实际输出吗？ - Oliver Charlesworth

如果你想要除以无符号的值，至少在函数声明中说明一下。 - unwind

@David Hefferman 是的。这是一份作业。但至少我正在努力去完成它。 - Kei Nivky

@Jonathan Leffler 实际上，这段代码存在几个问题，但它们不需要处理。它们只是不会在应用程序中发生。 - Kei Nivky

@KeiNivky 没有批评之意。我只是想知道这样我们才能相应地标记问题。现在我们知道如何帮助你了。 - David Heffernan

Answer 1

您有一个4.28的定点数，想要除以另一个4.28的数。您可以通过将分母的精度减去分子的精度来找到除法后的精度。直接进行除法运算会得到4.28 - 4.28 = 0，没有任何有效位。显然这样不行。

     1.5  [4.28] 0x18000000 
   / 2.0  [4.28] 0x20000000 
   =  0?  [0.00] 0x00000000

最理想的方法是将分子提升到8.56（通过乘以2^28），然后进行64位除法：

                     .   .   .   .
     1.5  [8.56] 0x180000000000000
   / 2.0  [4.28]        0x20000000 
   = 0.75 [4.28]        0x0c000000

如果您确实无法使用64位数字，那么您唯一的选择就是减少分母。例如，您可以通过除以2^14来使用一半的精度。

     1.5  [4.28] 0x18000000 
   / 2.0  [2.14]     0x8000
   = 0.75 [2.14]     0x3000

您可以将结果乘以相同的因子，以得到4.28数字：0x3000 *(1<<14) = 0x0c000000 这样做会损失一些精度，但如果不使用更大的分子，这是无法避免的。例如：5.0/3.0 = 1.66667 = 0x1AAAAAA [4.28]，但是
((5.0<<28)/(3<<14))<<14 = 0x1AAA8000 [4.28] = 1.66662

- AShelly

---

我想用我的方式会更好。不使用5位整数部分的目的是为了避免精度损失，而你的算法损失比我的1位还要大。 - Kei Nivky

你的方法更准确，但速度比较慢。通常使用定点运算是为了在浮点数计算较慢的处理器上提高速度。但如果你需要精度，你的方法是最好的。我认为至少会丢失一位二进制位。 - AShelly

Answer 2

正如此处所指出的（例如：将整数乘以常数的倒数），您可以通过使用乘法重新实现除法。之后，您应该能够用4位表示整数部分。

- Sebastian Dressler

---

你的链接是否使用完整精度执行逆运算和乘法？如果是这样，那么这种方法行不通——你的方法会舍入“正确”的答案，而不是执行定点除法。两种方法通常会产生不同的结果。 - EML