取模运算符（%）实际上是如何计算的？

Question

最近我对取模运算符%感到困惑。

已知当我们有整数a和b，其中a > b时，a % b == a-a/b*b。如果a和b足够小，我们可以手动进行这个计算。

然而，当涉及到处理器的计算方式时，处理器是否使用与之前提到的相同方法a-a/b*b？也许只是通过将除法转换为减法或加法，或者可能涉及一些移位吗？

- pNok

---

@BlackBear，如果它正在进行整数运算，则不是这样的。如果a为8，b为3，则a/b为2，因此a - (a/b)b = 8 - 23 = 2。 - Paul Tomblin

@BlackBear 抱歉，我应该明确说明一下，/和*是整数运算符，这意味着9/2==4和(9/2)*2==8，就像在C语言中一样。 ;) - pNok

@0ADD：我认为这是一个不同的问题。你提供的链接询问运算符的作用，而这个问题似乎是在询问它在处理器中如何实现。 - tinman

Answer 1

除了2的幂次方，取模运算符可以（在大多数优化编译器中）转换为简单的位运算，我恐怕唯一的方法就是走弯路。解释请参见http://en.wikipedia.org/wiki/Modulo_operation 在另一个答案中，@Henk Holterman指出，一些CPU在微码中执行它，将余数留在寄存器中进行整数除法，这意味着模数指令可以被减少到整数除法并返回余数。（我添加这个信息是因为这个答案已经被接受了。）

- Paul Tomblin

---

那么，如果模数不是2的幂，则处理取模运算的一般方法将与除法和余数相同。谢谢您的回复~ - pNok

并不是这样的，例如在x86架构中有IDIV指令，这里有一个页面。 - H H

@HenkHolterman，我更新了我的回答并包含了你的部分。 - Paul Tomblin

Answer 2

它使用了 idiv 汇编指令：

    int x = a % b;
00000050  cmp         dword ptr [rsp+20h],80000000h 
00000058  jne         0000000000000061 
0000005a  cmp         dword ptr [rsp+24h],0FFFFFFFFh 
0000005f  je          0000000000000070 
00000061  mov         eax,dword ptr [rsp+20h] 
00000065  cdq              
00000066  idiv        eax,dword ptr [rsp+24h] 
0000006a  mov         dword ptr [rsp+2Ch],edx 
0000006e  jmp         0000000000000075 
00000070  call        FFFFFFFFF2620E70 
00000075  mov         eax,dword ptr [rsp+2Ch] 
00000079  mov         dword ptr [rsp+28h],eax 

idiv指令将余数存储在一个寄存器中。
http://pdos.csail.mit.edu/6.828/2007/readings/i386/IDIV.htm

- Steve Wellens

---

我怀疑它在ARM或Motorola CPU上能否做到。但这是一个有效的例子。 - H H

我很想知道他们正在检查和调用某些东西的特殊情况是什么。我想知道是否是MIN_INT％MAX_INT？ - Paul Tomblin

@HenkHolterman @Steve Wellens：嗯，也许这里的idiv提供了另一层抽象？因为这会引发另一个问题，即如何实现idiv指令。正如我上面提到的，除法运算被转化为多次减法。当我们说CPU通过微码执行模运算时，实际上回答的是谁来执行以及在哪个层级上执行这个问题，而不是如何执行。即使微码执行它，我怀疑它是否采用了我们在高层级中使用的相同机制。 - pNok

那是一个硬件问题。你需要在另一个论坛上发布这个问题。 - Steve Wellens

@pNok，您似乎在想关于模数在硬件层面上是如何计算的。简短的回答是这很复杂。长的回答是您需要学习抽象层。http://en.wikipedia.org/wiki/Abstraction_layer 。为了友好的介绍，请观看“CPU的工作原理”http://www.youtube.com/watch?v=cNN_tTXABUA。 - hexicle

此答案仅适用于x86架构。 - Nirvana