为什么 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

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

\n

该运算符的行为是a/b向零舍入并a%b返回一个等于的数字(a/b)*a + a%b（a参见 ISO/IEC 9899:2011 \xc2\xa76.5.5 \xc2\xb66）。由于 \xe2\x80\x9c 朝零\xe2\x80\x9d 舍入意味着对负结果向上舍入，对正结果向下舍入，这实际上意味着余数采用分子的符号。

\n

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

\n

movl    -4(%rbp), %eax  # load numerator x\ncltd                    # edx = x >= 0 ? 0 : -1\nshrl    $29, %edx       # edx = x >= 0 ? 0 :  7\naddl    %edx, %eax      # eax = x >= 0 ? x : x + 7\nandl    $7, %eax        # eax = x >= 0 ? x&7 : x-1 & 7\nsubl    %edx, %eax      # eax = x >= 0 ? x&7 : (x-1 & 7) - 7\n

\n

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

\n

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

\n

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

\n