2

我正在为具有快速整数运算而不是快速浮点运算的微处理器编写代码。我需要将整数除以 1 到 9 的数字，然后将结果转换回整数。

我制作了一个浮点数组，其中包含 0、1、0.5、0.3333 等成员。但我认为除 (1/3) 之外的数字有 MAGIC 常量（如 0x55555556）。

这是什么数字？

4

2 回答 2

4

如果您的微控制器上的除法指令足够快，请使用它。如果您需要结果的小数部分，您可以使用余数；在大多数体系结构中，除法指令将商放在一个寄存器中，将余数放在另一个寄存器中。

如果您的除法指令不够快但乘法指令足够快，您可以使用以下技术（听起来好像这是您所追求的技术）。在大多数架构上，将一个 32 位数字乘以另一个 32 位数字会得到 64 位结果；较高的一半存储在一个寄存器中，而较低的一半存储在另一个寄存器中。您可以通过意识到除以数字 n 与乘以 (2^32)/n 相同，然后取结果的更重要的 32 位来利用这一点。换句话说，如果你想除以 3，你可以乘以 0x100000000/3 = 0x55555555，然后取结果中更高的 32 位。

您在这里所做的实际上是一种定点算术形式。查看Wikipedia 文章以获取更多信息。

于 2009-10-21T12:47:11.683 回答
1

我假设，基于微控制器标签，您没有快速整数除法。我的答案也适用于无符号值——它适用于有符号值，你只需要限制下面棘手的位中使用的数字。

一个好的开始是除以 2、4 和 8。假设您的 CPU 具有逻辑右移指令，这些可以分别通过 1、2 和 3 位的右移来完成。

其次，除以 1 只是保持数字不变。只剩下 3、5、6、7 和 9。

棘手的一点从这里开始：

对于其他数字，您可以使用除法可以替换为乘法和移位的事实。

假设您有一个 16 位处理器。要除以 N，乘以 256/N 并右移 8 位：

N = 3, multiply by 85
N = 5, multiply by 51
N = 6, multiply by 43
N = 7, multiply by 37
N = 9, multiply by 28

以 72 / 5 为例。将 72 乘以 51 得到 3672，然后右移 8 位得到 14。

为了使它起作用，您使用的数字不得溢出 16 位。由于最坏的情况是乘以 85，因此您可以处理高达 771 的数字。

之所以可行，是因为 8 位右移与除以 256 相同，并且：

  m * (256 /  n) / 256
= m / (n /  256) / 256
= m /  n *  256  / 256
= m /  n * (256  / 256)
= m /  n

如果您有 32 位处理器，则值和范围会有所变化，因为它是 65536/N：

N = 3, multiply by 21,846, right shift 16 bits, max value roughly 196,600.
N = 5, multiply by 13,108.
N = 6, multiply by 10,923.
N = 7, multiply by  9,363.
N = 9, multiply by  7,282.

同样，让我们​​选择随机的 20,000 / 7：20,000 乘以 9,363 是 187,260,000，当您右移 16 位时，您会得到 2,857 - 实际结果是 2,857。

以下 C 语言测试程序显示了给定值的准确度数据。它使用有符号值，因此最多只能达到 98,000 左右，但您可以看到最大误差是 1，并且它发生在 13,110 的低点（只有 0.008% 的误差）。

#include <stdio.h>
int res[5] = {0};
int low[5] = {-1,-1,-1,-1,-1};
int da[] = {3,5,6,7,9};
int ma[] = {21846,13108,10923,9363,7282};
int main (void) {
    int n, i;
    for (n = 0; n < 98000; n++) {
        for (i = 0; i < sizeof(da)/sizeof(da[0]); i++) {
            int r1 = n / da[i];
            int r2 = (n * ma[i])>>16;
            int dif = abs (r1-r2);
            if (dif >= 5) {
                printf ("%d / %d gives %d and %d\n", n, da[i], r1, r2);
                return 1;
            }
            res[dif]++;
            if (low[dif] == -1) {
                low[dif] = n;
            }
        }
    }
    for (i = 0; i < sizeof(res)/sizeof(res[0]); i++) {
        printf ("Difference of %d: %6d, lowest value was %6d\n", i, res[i], low[i]);
    }
    return 0;
}

这输出：

Difference of 0: 335874, lowest value was      0
Difference of 1: 154126, lowest value was  13110
Difference of 2:      0, lowest value was     -1
Difference of 3:      0, lowest value was     -1
Difference of 4:      0, lowest value was     -1
于 2009-10-21T12:44:52.047 回答