使用位移重新实现模数？

Question

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

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

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

编辑:其实我意识到我需要每秒超过180次.看作输入值可以是一个非常大的数字,最多40位数.

Answer 1

使用简单的按位运算可以做的是通过将它与除数-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是),我们需要将它递减1(从4到3的十进制),这就产生了位模式00000011.在我们对原始的123和3进行按位与AND之后,得到的位模式将是00000011.结果是十进制的3.我们需要二次幂除数的原因是,一旦我们将它们减1,我们就会得到所有不太重要的位1,其余的都是0.一旦我们进行按位-AND,它就会"取消"原始值中更重要的位,并简单地将原始值的剩余部分除以除数.

但是,除非事先知道你的除数(在编译时,甚至需要除数特定的代码路径),否则对任意除数应用这样的特定事物是行不通的 - 解析它的运行时是不可行的,尤其不是在你的情况下表现很重要.

还有一个与该主题相关的先前问题,从不同的角度可能有关于该问题的有趣信息.