c - 为什么 mod 2^n 对有符号数使用 CLTD 指令

Question

所以我知道，当您对无符号运算执行 x mod 2^n 时，编译器只会将该操作转换为 x & (2^n - 1)。

但是当我使用有符号数字查看编译器实现时，例如

int signed_rem8(int x) { return x %8; }

我得到这样的东西(https://godbolt.org/z/xY3Ef6WEc):

 movl    -4(%rbp), %eax
 cltd
 shrl    $29, %edx
 addl    %edx, %eax
 andl    $7, %eax
 subl    %edx, %eax

这背后的逻辑是什么？

Answer 1

这是由于负数模运算符的行为造成的。

此运算符的行为是，a/b 向零舍入，并且 a%b 返回一个数字，使得 (a/b)* a + a%b 等于 a(参见 ISO/IEC 9899:2011 §6.5.5 ¶6)。由于“向零舍入”意味着对负结果向上舍入，对正结果向下舍入，这实际上意味着余数采用分子的符号。

为了正确实现此行为，编译器使用 cltd 指令(将 eax 符号扩展为 edx:eax)，如下所示:

movl    -4(%rbp), %eax  # load numerator x
cltd                    # edx = x >= 0 ? 0 : -1
shrl    $29, %edx       # edx = x >= 0 ? 0 :  7
addl    %edx, %eax      # eax = x >= 0 ? x : x + 7
andl    $7, %eax        # eax = x >= 0 ? x&7 : x-1 & 7
subl    %edx, %eax      # eax = x >= 0 ? x&7 : (x-1 & 7) - 7

因此，如果是正数，我们会得到 0 到 7 范围内的正余数，而如果是负数，我们会得到 -7 到 0 范围内的负余数。

在这两种情况下，余数在数字上都是正确的，因为余数应该是残数类 x mod 8 的表示，正余数和负余数都是如此。

您可能会看到其他编译器使用稍微不同的代码来解决这个问题，但总体思路是相似的。