6

整数除法/和模%运算经常在编程中一起使用，有时甚至在相同的操作数和后续行中。例如，下面的 C 函数是一个简单的函数，它将/2 个数字的结果与它们的结果相加%，它就是这样做的： 

int sum2digits(int x, int base) {
    int n, m;
    n = x / base;
    m = x % base;
    return n + m;
}

据我所知，两者/和%都由相同的机器指令（在x86中）执行。比如说，如果您执行机器指令对两个数字和进行整数除法 (div或) ，然后 的值将存储在寄存器 EAX 中，余数存储在 EDX 中。 我想知道编译器是否利用了这种质量并查看了汇编代码。事实证明，使用 gcc 进行正常编译并不会对此进行优化： idivaba / ba % b

push   %rbp
mov    %rsp,%rbp
mov    %edi,-0x14(%rbp)
mov    %esi,-0x18(%rbp)
mov    -0x14(%rbp),%eax
mov    %eax,%edx
sar    $0x1f,%edx
idivl  -0x18(%rbp)
mov    %eax,-0x8(%rbp)
mov    -0x14(%rbp),%eax
mov    %eax,%edx
sar    $0x1f,%edx
idivl  -0x18(%rbp)
mov    %edx,-0x4(%rbp)
mov    -0x4(%rbp),%eax
mov    -0x8(%rbp),%edx
add    %edx,%eax
pop    %rbp
retq

此汇编代码对 idivl 执行 2 次后续调用，但每次都从另一个寄存器读取结果（EAX 表示商，EDX 表示余数）。但是，编译时会-O改变图片： 

mov    %edi,%eax
mov    %edi,%edx
sar    $0x1f,%edx
idiv   %esi
add    %edx,%eax
retq

此代码idiv仅调用一次，并将其值用于两次计算。
为什么这种优化不是默认的？div连续调用两次有什么用？这种优化能以任何方式改变程序的行为吗？
此外，也许更重要的是，作为程序员，有没有办法手动提取这 2 个值（商和余数），以保证 CPU 只执行 1 个整数除法？

4

3 回答 3

4

为什么这种优化不是默认的？

如果编译器和优化器是完美的并且调试器可以对代码进行逆向工程，那么优化将是一个普遍的默认设置。但是编译器并不总是生成正确的代码，优化器并不总是保留语义，调试器也不能总是弄清楚任何给定指令与优化程序的哪些部分相关。看起来您的编译器安装了默认选项，以确保绝对安全和调试简单。

有没有办法手动提取这两个值（商和余数）以保证 CPU 只执行 1 个整数除法？

如今，最好的方法正是您所做的：向编译器询问优化的代码。该div例程是从除法运算符的结果被定义为负数的实现和优化编译非常缓慢以至于识别这样的事情最好手动完成的日子的保留。

于 2013-04-10T03:14:43.627 回答
2

为什么不直接使用 div？

http://www.cplusplus.com/reference/cstdlib/div/

我会说这是优化便携式解决方案的最佳机会？

致删除我答案的人：请不要删除此答案！如果必须投反对票，或者评论为什么它如此错误以至于您认为需要删除它。

OP 想了解使用 C 对整数除法和模（余数）的后续调用进行优化。

所以，如果你想在你的代码中达到最优，为什么不使用标准库调用，将优化的责任交给标准库实现者，他们可能对编译器的内部工作和本机机器的可用操作有更好的信息（即在 x86 上使用 div 汇编指令）。尤其是当函数完全符合 OP 试图做的事情时。

如果我在实际代码中看到一个除法后跟一个 mod，我的直接问题将是“你为什么不使用标准库？”，而不是“嗯，我想知道编译器如何优化我的高级代码？ ”。

它还回答了问题的一部分：此外，也许更重要的是，作为程序员，有没有办法手动提取这 2 个值（商和余数），以保证 CPU 只执行 1 个整数除法？

于 2013-04-10T07:55:12.207 回答
2

你总是可以实现自己的部门：

#include <stdlib.h>
#include <stdio.h>

void mydiv(int dividend, int divisor, int* quotient, int* remainder)
{
  *quotient = dividend / divisor;
  *remainder = dividend - *quotient * divisor;
}

int testData[][2] =
{
  { +5, +3 },
  { +5, -3 },
  { -5, +3 },
  { -5, -3 },
};

int main(void)
{
  unsigned i;
  for (i = 0; i < sizeof(testData)/sizeof(testData[0]); i++)
  {
    div_t res1, res2;
    res1 = div(testData[i][0], testData[i][1]);
    mydiv(testData[i][0], testData[i][1], &res2.quot, &res2.rem);
    printf("%+d/%+d = %+d:%+d %c= %+d:%+d\n",
           testData[i][0], testData[i][1],
           res1.quot, res1.rem,
           "!="[res1.quot == res2.quot && res1.rem == res2.rem],
           res2.quot, res2.rem);
  }
  return 0;
}

输出（ideone）：

+5/+3 = +1:+2 == +1:+2
+5/-3 = -1:+2 == -1:+2
-5/+3 = -1:-2 == -1:-2
-5/-3 = +1:-2 == +1:-2

这确实有一个部门。但是，看起来 gcc 不够聪明，无法消除乘法，因此您各有一个。

于 2013-04-09T21:39:59.683 回答