我正在为一个非常有限的系统编写代码，其中模运算非常缓慢。在我的代码中，每秒需要使用模约180次，我想尽可能地减少其使用次数，以显著提高代码的速度。目前我的主循环一次不像应该的那样在1/60秒内运行完。我想知道是否有可能仅使用位移操作重新实现模运算，就像使用乘法和除法一样。以下是我的c++代码（如果可以使用汇编来执行模运算，那就更好了）。如何在不使用除法或乘法的情况下删除模操作？
while(input > 0)
{
out = (out << 3) + (out << 1);
out += input % 10;
input = (input >> 8) + (input >> 1);
}
编辑：实际上我意识到我需要每秒超过180次以上的操作。因为输入值可能是一个长达40位数字的非常大的数。
使用简单的位运算，您可以通过将值（被除数）与除数-1进行AND运算来取模（除法）2的幂。以下是几个例子：
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).
1111011和除数4的位模式00000100为例。正如我们现在所知道的，除数必须是2的幂次方（如4），并且我们需要将其减1（从10进制的4变为3），得到的位模式为00000011。在我们对原始值123和3进行按位与运算后，得到的结果位模式将是00000011。这在十进制中等于3。之所以需要一个2的幂次方除数，是因为一旦我们将其减1，就会得到所有较低有效位设置为1，其余位为0。一旦我们执行按位与运算，它会“抵消”原始值的更高有效位，并仅留下原始值除以除数的余数。实际上，通过常量进行除法是编译器中已知的一种优化方法，事实上，gcc已经在使用该方法。
这段简单的代码：
int mod(int val) {
return val % 10;
}
在我比较老的gcc上使用-O3，会生成以下代码：
_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
使用位移进行模10运算将会很困难和丑陋，因为位移在任何现代计算机上都是二进制的。如果你仔细想一下，位移实际上就是乘以2或除以2。
但是这里有一个明显的时空权衡：设置一个out和out%10值的表格并查找它。然后这行代码就变成了：
out += tab[out]
如果运气好的话，这将变成一个16位加法和存储操作。
16的每个幂都以6结尾。如果您将数字表示为16的幂的总和（即将其分解为nybbles），则除了个位数之外，每个术语都以相同的方式对最后一位数字产生贡献。
0x481A % 10 = ( 0x4 * 6 + 0x8 * 6 + 0x1 * 6 + 0xA ) % 10
0x481A % 10 = ( 0x4 + 0x8 + 0x1 /* sum = 13 */
+ 5 /* so add 5 */ + 0xA /* and the one's place */ ) % 10
= 28 % 10
这将16位、4个nybble模数减少到最多0xF * 4 + 5 = 65。在二进制中，这仍然很烦人，因此您需要重复算法（尽管其中一个不算）。
但是，286应该具有相当高效的BCD加法，您可以使用它来执行求和并一次性获得结果。（这需要手动将每个nybble转换为BCD；我对该平台的了解还不足以说明如何优化或是否存在问题。）