高效mod 3在x86装配中的应用

Question

DIV指令在现代处理器上是昂贵的。在x86程序集中是否有更快的方法来减少64位整数mod 3？

Answer 1

有一些算法是基于乘法除法和除数的倒数。在这方面有各种文件，其中最常引用的一篇是：

作者声明: Peter L.“用乘法除以不变整数。”ACM SIGPLAN通知。第29卷，第6号，1994年8月，第61-72页(在线)

当打开优化时，您的C/C++编译器很可能已经使用了该算法的一个变体。例如，我的Intel编译器version 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