c++ - 使用位移重新实现模？

Question

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

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

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

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

Answer 1

simple 位运算可以做的就是通过与除数 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 .一旦我们进行按位与运算，它就会从原始值中“消除”更高的有效位，并且只剩下原始值除以除数的余数。

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

还有a previous question related to the subject这可能从不同的角度对此事有有趣的信息。