13

我正在为一个非常有限的系统编写一些代码，其中 mod 运算符非常慢。在我的代码中，模数需要每秒使用大约 180 次，我认为尽可能多地删除它会显着提高我的代码速度，截至目前，我的 mainloop 的一个周期不会以 1/60 的速度运行第二，它应该。我想知道是否可以仅使用位移来重新实现模数，就像乘法和除法一样。所以这是我迄今为止在 C++ 中的代码（如果我可以使用汇编执行模数，那就更好了）。如何在不使用除法或乘法的情况下删除模数？

    while(input > 0)
{
    out = (out << 3) + (out << 1);
    out += input % 10;

    input = (input >> 8) + (input >> 1);
}

编辑：实际上我意识到我需要每秒执行超过 180 次。看到输入的值可以是一个非常大的数字，最多 40 位。

4

5 回答 5

22

您可以使用简单的按位运算执行的操作是将值（除数）与除数 1 进行“与”运算，以取值（除数）的二次幂模（除数）。几个例子：

unsigned int val = 123; // initial value
unsigned int rem;

rem = val & 0x3; // remainder after value is divided by 4. 
                 // Equivalent to 'val % 4'
rem = val % 5;   // remainder after value is divided by 5.
                 // Because 5 isn't power of two, we can't simply AND it with 5-1(=4).

为什么它有效？让我们考虑值 123 的位模式，1111011然后是除数 4，其位模式为00000100。正如我们现在所知道的，除数必须是 2 的幂（如 4），我们需要将其减一（从十进制的 4 到 3），这产生了位模式00000011。在我们对原始的 123 和 3 进行按位与后，得到的位模式将是00000011. 结果是十进制的 3。我们需要二的幂除数的原因是，一旦我们将它们减一，我们就会将所有次要有效位设置为1，其余为0。一旦我们进行按位与运算，它就会从原始值中“消除”更高的有效位，而只剩下原始值除以除数的余数。

但是，除非您事先知道除数（在编译时，甚至需要特定除数的代码路径），否则对任意除数应用这样的特定内容是行不通的 - 在运行时解决它是不可行的，尤其是在您的情况下性能很重要。

还有一个与该主题相关的先前问题，它可能从不同的角度提供有关该问题的有趣信息。

于 2012-06-18T05:05:24.667 回答
4

实际上，除以常量是编译器众所周知的优化，事实上，gcc 已经在这样做了。

这个简单的代码片段：

int mod(int val) {
   return val % 10;
}

使用 -O3 在我相当旧的 gcc 上生成以下代码：

_mod:
        push    ebp
        mov     edx, 1717986919
        mov     ebp, esp
        mov     ecx, DWORD PTR [ebp+8]
        pop     ebp
        mov     eax, ecx
        imul    edx
        mov     eax, ecx
        sar     eax, 31
        sar     edx, 2
        sub     edx, eax
        lea     eax, [edx+edx*4]
        mov     edx, ecx
        add     eax, eax
        sub     edx, eax
        mov     eax, edx
        ret

如果您忽略功能后记/序言，则基本上是两个 muls（实际上在 x86 上我们很幸运，可以使用 lea 作为一个）和一些转变和添加/子。我知道我已经在某个地方解释了这个优化背后的理论，所以我会在再次解释之前看看我是否能找到那个帖子。

现在在现代 CPU 上，这肯定比访问内存要快（即使你命中了缓存），但是对于你显然更古老的 CPU 来说，它是否更快是一个只能通过基准测试来回答的问题（并且还要确保你的编译器正在做该优化，否则您总是可以在这里“窃取” gcc 版本；））。特别是考虑到它依赖于有效的 mulhs（即乘法指令的更高位）才能有效。请注意，此代码与大小无关- 确切地说是幻数更改（也可能是添加/移位的一部分），但可以调整。

于 2012-06-18T20:50:53.680 回答
2

对位移进行模 10 运算将变得困难且丑陋，因为位移本质上是二进制的（在您今天将要运行的任何机器上）。如果您考虑一下，位移只是简单地乘以或除以 2。

但是您可以在这里进行明显的时空交易：为 和 设置一个值表out并out % 10进行查找。然后这条线变成

  out += tab[out]

如果运气好的话，那将是一个 16 位的加法和存储操作。

于 2012-06-18T02:12:45.667 回答
1

如果你想做模 10 和班次，也许你可以根据你的需要调整双涉猎算法？

该算法用于将二进制数转换为十进制数，而不使用模数或除法。

于 2012-06-18T05:43:31.337 回答
1

16 的每个幂都以 6 结尾。如果您将数字表示为 16 的幂的总和（即，将其分解为 nybbles），那么每个项都以相同的方式对最后一个数字做出贡献，除了个位。

0x481A % 10 = ( 0x4 * 6 + 0x8 * 6 + 0x1 * 6 + 0xA ) % 10

请注意，6 = 5 + 1，如果有偶数个，5 将抵消。因此，只需将 nybbles 相加（最后一个除外），如果结果为奇数，则加 5。

0x481A % 10 = ( 0x4 + 0x8 + 0x1 /* sum = 13 */
                + 5 /* so add 5 */ + 0xA /* and the one's place */ ) % 10
            = 28 % 10

这将 16 位、4 位模的模数减少到最多0xF * 4 + 5 = 65. 在二进制中，这仍然是令人讨厌的 3 个 nybbles，因此您需要重复该算法（尽管其中一个并不算数）。

但是 286 应该具有相当有效的 BCD 加法，您可以使用它来执行求和并一次获得结果。（这需要手动将每个 nybble 转换为 BCD；我对平台了解得不够多，无法说明如何优化它或者它是否有问题。）

于 2012-06-18T10:24:18.667 回答