重新使用移位实现模？ [英] re implement modulo using bit shifts?

问题描述

我在写一些code非常有限的系统，其中Mod运算速度非常慢。在我的codeA模需要每秒要使用约180倍，我想，删除它尽可能多地将显著增加我的code的速度，现在我的一个主循环不会运行在周期1/60秒，因为它应该。我想知道，如果只使用移位喜欢的是可能的乘法和除法有可能重新实现模。因此，这里是我的code到目前为止，在C ++（如果我可以执行使用汇编的话会更好模）。如何删除不使用乘除模？

I'm writing some code for a very limited system where the mod operator is very slow. In my code a modulo needs to be used about 180 times per second and I figured that removing it as much as possible would significantly increase the speed of my code, as of now one cycle of my mainloop does not run in 1/60 of a second as it should. I was wondering if it was possible to re-implement the modulo using only bit shifts like is possible with multiplication and division. So here is my code so far in c++ (if i can perform a modulo using assembly it would be even better). How can I remove the modulo without using division or multiplication?

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

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

编辑：其实我意识到我需要做的方式超过180次每秒。看到，因为输入的值可以是一个非常大的数量最多为40个数字。

Actually I realized that I need to do it way more than 180 times per second. Seeing as the value of input can be a very large number up to 40 digits.

推荐答案

您可以使用的简单的位操作，​​走的是值的功率为2的模（除数）做什么（股息）通过与除数-1 AND'ing的吧。举几个例子：

What you can do with simple bitwise operations is taking a power-of-two modulo(divisor) of the value(dividend) by AND'ing it with divisor-1. A few examples:

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 。正如我们所知道现在，除数必须是乘方的两（如4），我们需要一个（从4到十进制3）递减它这产生我们的位模式 00000011 。我们按位与后两个原始123和3中，所得到的位模式将是 00000011 。这原来是十进制3。为什么我们需要功率为2的除数的原因是，一旦我们减一他们，我们得到了所有设置为 1 少显著位，其余均为 0 。一旦我们这样做按位与，它抵消了从原来的值更显著位，留给我们除以除数原值的根本其余部分。

Why it works? Let's consider a bit pattern for the value 123 which is 1111011 and then the divisor 4, which has the bit pattern of 00000100. As we know by now, the divisor has to be power-of-two(as 4 is) and we need to decrement it by one(from 4 to 3 in decimal) which yields us the bit pattern 00000011. After we bitwise-AND both the original 123 and 3, the resulting bit pattern will be 00000011. That turns out to be 3 in decimal. The reason why we need a power-of-two divisor is that once we decrement them by one, we get all the less significant bits set to 1 and the rest are 0. Once we do the bitwise-AND, it 'cancels out' the more significant bits from the original value, and leaves us with simply the remainder of the original value divided by the divisor.

但是，应用特定像这样的东西任意除数是行不通的，除非你知道你的除数事先（在编译时，甚则需要特定的除数codepaths） - 解决它运行时是不可行，尤其不要在你的情况下的性能问题。

However, applying something specific like this for arbitrary divisors is not going to work unless you know your divisors beforehand(at compile time, and even then requires divisor-specific codepaths) - resolving it run-time is not feasible, especially not in your case where performance matters.

也有<一个href=\"http://stackoverflow.com/questions/980702/efficient-cycles-wise-algorithm-to-compute-modulo-25\">a $ P $涉及这可能对来自不同角度的事有趣的信息主题 pvious问题。

Also there's a previous question related to the subject which probably has interesting information on the matter from different points of view.

这篇关于重新使用移位实现模？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！