有没有c++函数（内置或其他）可以给出整数除法和模除法结果而不重复运算？

Question

您可以这样写：

int i = 3;
int k = 2;
int division = i / k;
int remainder = i % k;

似乎认为这会在较低的级别上要求 ALU 执行两项视觉操作：一项返回商，一项返回余数。然而，我相信 ALU 很可能会在一次操作中计算这两者。如果是这种情况，这并不是最佳效率。

有没有更有效的方法来做到这一点，而不要求CPU计算两次？换句话说，可以通过 C++ 的单个操作来完成吗？

Answer 1

实际上，您编写的代码不会生成任何除法指令，因为编译器可以在编译时计算出结果。我编写了一个小测试程序并设置编译器（VC++ 10SP1）来生成汇编代码列表。

#include <iostream>

using namespace std;

struct result {
    long quotient, remainder;
};

result divide(long num, long den) {
    result d = { num / den, num % den };
    return d;
}

int main() {
    result d = divide(3, 2);
    d = divide(10, 3);
    cout << d.quotient << " : " << d.remainder << endl;
    return 0;
}

我必须这样编写它并明确告诉编译器不要内联任何函数。
否则编译器会很高兴地优化掉大部分代码。这是除法函数的最终汇编代码。

; 8    : result divide(long num, long den) {

  00000 55       push    ebp
  00001 8b ec        mov     ebp, esp

; 9    :     result d = { num / den, num % den };

  00003 99       cdq
  00004 f7 7d 08     idiv    DWORD PTR _den$[ebp]

; 10   :     return d;
; 11   : }

  00007 5d       pop     ebp
  00008 c3       ret     0

它足够智能，可以生成单个 IDIV 指令并使用它生成的商和余数。现代 C 和 C++ 编译器非常擅长这种优化。除非您遇到性能问题并且已经分析了代码以确定瓶颈所在，否则不要尝试再次猜测编译器。

Answer 2

ISO C99 具有 ldiv 功能：

#include <stdlib.h>

ldiv_t ldiv(long numer, long denom);

The ldiv() function computes the value numer/denom (numerator/denominator).
It returns the quotient and remainder in a structure named ldiv_t that contains
two long members named quot and rem.

是否在 FPU 级别减少到单个操作我不能说。

Answer 3

当然：

int i = 3;
int k = 2;
int division = i / k;
int remainder = i - division * k;

另外，如果您确实想这样做，请查看 div，我怀疑它是否更快，就像我上面的解决方案一样。

Answer 4

我不知道任何内置的东西，但你可以用乘法而不是除法来模拟它：

int division = i / k;
int remainder = i - (division * k);

Answer 5

当你问自己什么是最快时，通常最好对其进行基准测试（我喜欢这样做）。因此，我从这里获取了答案，编写了一个小型基准测试程序，并将其扔到 gcc 上（我认为 g++ 应该有类似的结果）在 -O0< /code> （在 -O1 他优化了所有内容，我的基准测试被破坏了）。

我执行了 2^28 运行（i 和 k 均从 1 运行到 2^14< /code>) 在我的笔记本电脑上运行，得到以下运行时间：

division = 0;
remainder = 0;
// this test is only there to measure the constant overhead!

1.676s

division = i/k;
remainder = i%k;

24.614s

division = i/k;
remainder = i - division*k;

15.009s

ldiv_t d = ldiv(i,k);
division = d.quot;
remainder = d.rem;

18.845s

正如我们所看到的，存在差异，最好的办法是乘法 方法。 ldiv 方法也不错，但我发现它与其他方法相比稍微麻烦一些。