获得整数 mod 10 和整数除以 10 的最快方法？

电器工程 微控制器 模拟 优化 算术除法
2022-01-27 06:53:16

如果硬件不支持模数或除法运算，则需要更多的 CPU 周期来通过软件模拟模数/除法。如果操作数是 10，有没有更快的方法来计算除法和模数？

在我的项目中，我经常需要计算整数模数 10。特别是，我正在研究 PIC16F，需要在 LCD 上显示一个数字。支持 4 位数字，因此有 4 次调用模数和除法函数（软件实现）。也就是说，如下所示：

digit = number % 10;    // call to an expensive function
number /= 10;           // call to an expensive function
somehow_lit_segments();

digit = number % 10;    // call to an expensive function
number /= 10;           // call to an expensive function
somehow_lit_segments();

digit = number % 10;    // call to an expensive function
number /= 10;           // call to an expensive function
somehow_lit_segments();

digit = number % 10;    // call to an expensive function
number /= 10;           // call to an expensive function
somehow_lit_segments();

还有其他领域使用类似的代码。

4个回答

这是我几年前使用的二进制到 BCD 算法，基于此处找到的算法。我使用的是外部 BCD 到 7 段显示驱动程序，因此可以将结果作为打包的 BCD 直接写入正确的端口以进行输出。

如果您在 PIC 中有硬件乘法器，这相当快，我使用的是 PIC18F97J60。如果您的 PIC 上没有硬件乘法器，请考虑使用 shift + add 进行乘法运算。

这接受一个无符号的 16 位 int 并返回 5 位的压缩 BCD，它可以被修改并更快地用于 4 位。它使用 shift + 加法来近似除以 10，但考虑到有限的输入范围，它正好适合这种用途。您可能还希望以不同的方式打包结果，以符合您使用结果的方式。

void intToPackedBCD( uint16_t n, uint8_t *digits ) {
    
    uint8_t d4, d3, d2, d1, d0, q;  //d4 MSD, d0 LSD

    d1 = (n>>4)  & 0xF;
    d2 = (n>>8)  & 0xF;
    d3 = (n>>12) & 0xF;

    d0 = 6*(d3 + d2 + d1) + (n & 0xF);
    q = (d0 * 0xCD) >> 11;
    d0 = d0 - 10*q;

    d1 = q + 9*d3 + 5*d2 + d1;
    q = (d1 * 0xCD) >> 11;
    d1 = d1 - 10*q;

    d2 = q + 2*d2;
    q = (d2 * 0x1A) >> 8;
    d2 = d2 - 10*q;

    d3 = q + 4*d3;
    d4 = (d3 * 0x1A) >> 8;
    d3 = d3 - 10*d4;

    digits[0] = (d4<<4) | (d3);
    digits[1] = (d2<<4) | (d1);
    digits[2] = (d0<<4);
}

您可以使用double dabble 算法从二进制转换为压缩 BCD，而无需任何除法。它仅使用shift和add 3。

例如将 243 10 = 11110011 2转换为二进制

0000 0000 0000   11110011   Initialization
0000 0000 0001   11100110   Shift
0000 0000 0011   11001100   Shift
0000 0000 0111   10011000   Shift
0000 0000 1010   10011000   Add 3 to ONES, since it was 7
0000 0001 0101   00110000   Shift
0000 0001 1000   00110000   Add 3 to ONES, since it was 5
0000 0011 0000   01100000   Shift
0000 0110 0000   11000000   Shift
0000 1001 0000   11000000   Add 3 to TENS, since it was 6
0001 0010 0001   10000000   Shift
0010 0100 0011   00000000   Shift
   2    4    3
       BCD

当没有可用的硬件除数时，此算法非常有效。此外，仅使用左移 1，因此即使没有桶形移位器，它也很快

假设无符号整数，除法和乘法可以由位移形成。并且从（整数）除法和乘法中，可以导出模数。

乘以 10：

y = (x << 3) + (x << 1);

除以 10 更困难。我知道几种除法算法。如果我没记错的话，有一种方法可以使用位移和减法快速除以 10，但我不记得确切的方法。如果这不是真的，那么这是一个管理 <130 个周期的除法算法。我不确定你使用的是什么微，但你可以以某种方式使用它，即使你必须移植它。

编辑：有人在 Stack Overflow 上说，如果你能容忍一点错误并且有一个大的临时寄存器，这将起作用：

temp = (ms * 205) >> 11;  // 205/2048 is nearly the same as /10

假设你有除法和乘法，模很简单：

mod = x - ((x / z) * z)

根据您需要的位数，您可以使用蛮力方法（d- 输入数字，t- 输出 ASCII 字符串）：

t--;
if (d >= 1000) t++; *t = '0'; while (d >= 1000) { d -= 1000; *t += 1; }
if (d >= 100) t++; *t = '0'; while (d >= 100) { d -= 100; *t += 1;}
if (d >= 10) t++; *t = '0'; while (d >= 10) { d -= 10; *t += 1;}
t++; *t = '0' + d;

您还可以将多个 if 更改为循环，通过乘法或查找表获得 10 的幂。

其它你可能感兴趣的问题
上一篇旋转时直流玩具电机会发出交流电吗？ 下一篇为什么模运算会消耗更多功率？