剰余

Computer

x86_64 なマシンで以下の剰余を求めるコードのアセンブリを吐き出してみる。

unsigned int umod3(unsigned int n) { return n % 3; }
int          mod3(int n)           { return n % 3; }

% gcc -O2 -S mod.c

こんな感じ。

umod3:
        movl    %edi, %eax
        movl    $-1431655765, %edx
        mull    %edx
        shrl    %edx
        leal    (%rdx,%rdx,2), %edx
        subl    %edx, %edi
        movl    %edi, %eax
        ret

mod3:
        movl    %edi, %eax
        movl    $1431655766, %edx
        imull   %edx
        movl    %edi, %eax
        sarl    $31, %eax
        subl    %eax, %edx
        leal    (%rdx,%rdx,2), %edx
        subl    %edx, %edi
        movl    %edi, %eax
        ret

剰余って奥が深いな。というよりなんでこれで mod 3 が求まるんだろう。よくわからん。