C++求余用的“%”有与它效率相同的其它算法吗？

Answer 1

如果右侧为常数，可转换成乘法、右移和減法。现代的编译器都会做这个优化，例如

// mod.c
unsigned a = 123;
int main() { return a % 13; }

使用 clang -c -S mod.c 输出汇编

   movl    $13, %eax
    movl    $0, -4(%rbp)
    movl    _a(%rip), %ecx
    movl    %eax, -8(%rbp)          ## 4-byte Spill
    movl    %ecx, %eax
    xorl    %edx, %edx
    movl    -8(%rbp), %ecx          ## 4-byte Reload
    divl    %ecx
    movl    %edx, %eax

这是直接翻译，用 divl 做除数，这指令同时能获得余数（edx ），但 divl 是很慢的。

然而，使用优化的话 clang -c -S -O3 mod.c

   movl    _a(%rip), %eax
    imulq   $1321528399, %rax, %rcx ## imm = 0x4EC4EC4F
    shrq    $34, %rcx
    imull   $13, %ecx, %ecx
    subl    %ecx, %eax

解释一下，因为 1321528399 / 2^34 ≈ 1 / 13

 a % 13
= a - (a / 13) * 13
= a - uint32_t((uint64_t(a) * 1321528399ULL) >> 34) * 13

Answer 2

x mod y: while(x >= y) x -= y;
最终x就是要获得的结果，适用于x比y很大的时候。如果觉得行希望采纳，谢谢！