Как вычисляется оператор по модулю (%)?

Question

Недавно я запутался в операторе по модулю, %.

Известно, что a % b == a-a/b*b, когда у нас есть целые числа a и b, где a > b, и мы можем сделать этот расчет вручную, если a и b достаточно малы.

Однако, когда дело доходит до того, как процессор его вычисляет, использует ли процессор тот же метод, что и выше, a-a/b*b? Может быть, просто переводя деление на вычитание или сложение, или, может быть, есть какое-то изменение?

Answer 1

За исключением степеней 2, где оператор по модулю (и в большинстве оптимизирующих компиляторов) может быть превращен в простую побитовую операцию, я боюсь, что единственный способ сделать это - трудный путь.Объяснение: http://en.wikipedia.org/wiki/Modulo_operation

В другом ответе @Henk Holterman указывает, что некоторые процессоры делают это в микрокоде, оставляя остаток в регистре, выполняя целочисленное деление, что означает, что инструкцию по модулю можно уменьшить доцелочисленное деление и возврат остатка.(Я добавляю эту информацию сюда, потому что этот ответ уже принят.)

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