assembly - x86组装中的高效mod 3

DIV指令在现代处理器上很昂贵。有没有更快的方法来减少x86汇编中的64位整数mod 3？

最佳答案

基于与除数的倒数相乘进行除法的算法有很多。关于此的论文很多，其中最常引用的是:

TorbjörnGranlund和Peter L.Montgomery。 “使用乘法除以不变整数。” ACM SIGPLAN声明。卷1994年8月29日，第29页，第61-72页(online)

打开优化功能后，您的C/C++编译器很可能已经在使用此算法的变体。例如，我的Intel编译器版本13更改为:

#include <stdint.h>
uint64_t mod3 (uint64_t a)
{
    return a % 3;
}

到这里(我的行尾注解):

mod3    PROC
; parameter 1: rcx
        mov       r8, 0aaaaaaaaaaaaaaabH      ;; (scaled) reciprocal of 3
        mov       rax, rcx
        mul       r8                          ;; multiply with reciprocal
        shr       rdx, 1                      ;; quotient
        lea       r9, QWORD PTR [rdx+rdx*2]   ;; back multiply with 3
        neg       r9
        add       rcx, r9                     ;; subtract from dividend
        mov       rax, rcx                    ;; remainder
        ret
mod3    ENDP