同时进行除法和取余运算？

Question

显然，x86（以及可能许多其他指令集）将除法操作的商和余数都放在不同的寄存器中。

现在，我们可以相信编译器会将这样的代码优化为只使用一次除法调用：

( x / 6 )
( x % 6 )

他们很可能会这样做。不过，是否有任何 语言（或库，但主要是语言）支持同时给出除法和取模的结果？如果有，它们是什么，语法是什么样的？

- Ben

Answer 1

C语言有 div 和 ldiv 函数。它们是否会为商和余数生成单独的指令，取决于您所使用的标准库实现、编译器和优化设置。从C99开始，您还可以使用 lldiv 处理更大的数字。

- bta

---

有趣的是，在4.8中，模数本身并没有使用div实现：https://dev59.com/Mm855IYBdhLWcg3wZzff - Ciro Santilli OurBigBook.com

不要在当前编译器中使用此方法，尤其是用于除以常数：它无法进行优化。可以查看 https://godbolt.org/g/ydL27q ：div(var, 10) 编译成实际函数调用，并且 div 库实现不知道除数是一个常数的 10。因此，它不能使用乘法逆元。即使是对于运行时变量的除数，你也会得到更大的代码大小和在 x86 上的非内联函数调用。 - Peter Cordes

如果这些函数是必要的或常用的，编译器会内置它们（就像对于memcpy一样），但它们不是，因此它们的优化效果远不如它们本应该有的那么好。因此，最好只使用附近的n / d和n％d，并且n和d完全相同，以便编译器可以可靠地优化除以常数、常量传播和范围信息。（例如，编译器知道除以10的结果具有比完整的int范围更小的范围，从而可能允许它稍后进行优化。） - Peter Cordes

无论如何，这是对这个问题的一个很好的回答，但重要的是指出，除非您先在正在使用的编译器中实现快速支持，否则不应该实际使用语言的这一部分。 对于32位机器上的64位除法或其他无法直接内联微小内容的情况，gcc已经调用了内部的libgcc.a函数，因此您可能甚至从未使用这些函数来节省代码大小。 - Peter Cordes

我确实见过将div()函数调用进行优化，以便从单个DIV指令中获取两个结果，其中分开的 / 和 % 语句会有效地运行整个计算两次（我不记得是哪个编译器了，不过它是一个嵌入式平台）。如果x是volatile的，那么你的结果可能因为完全不同的原因而发生变化。再次强调，在对其进行优化之前，请始终使用特定用例测试与实现相关的行为。 - bta

Answer 2

Python可以做到。

>>> divmod(9, 4)
(2, 1)

这很奇怪，因为Python是一种高级语言。

Ruby也是如此：

11.divmod(3) #=> [3, 2]

*** 编辑 ***

需要注意的是，这些运算符的目的可能不是尽可能高效地完成工作，更有可能是为了正确性/可移植性而存在。

对于那些感兴趣的人，我相信这是Python整数divmod实现的代码：

static enum divmod_result
i_divmod(register long x, register long y,
     long *p_xdivy, long *p_xmody)
{
long xdivy, xmody;

if (y == 0) {
    PyErr_SetString(PyExc_ZeroDivisionError,
                    "integer division or modulo by zero");
    return DIVMOD_ERROR;
}
/* (-sys.maxint-1)/-1 is the only overflow case. */
if (y == -1 && UNARY_NEG_WOULD_OVERFLOW(x))
    return DIVMOD_OVERFLOW;
xdivy = x / y;
/* xdiv*y can overflow on platforms where x/y gives floor(x/y)
 * for x and y with differing signs. (This is unusual
 * behaviour, and C99 prohibits it, but it's allowed by C89;
 * for an example of overflow, take x = LONG_MIN, y = 5 or x =
 * LONG_MAX, y = -5.)  However, x - xdivy*y is always
 * representable as a long, since it lies strictly between
 * -abs(y) and abs(y).  We add casts to avoid intermediate
 * overflow.
 */
xmody = (long)(x - (unsigned long)xdivy * y);
/* If the signs of x and y differ, and the remainder is non-0,
 * C89 doesn't define whether xdivy is now the floor or the
 * ceiling of the infinitely precise quotient.  We want the floor,
 * and we have it iff the remainder's sign matches y's.
 */
if (xmody && ((y ^ xmody) < 0) /* i.e. and signs differ */) {
    xmody += y;
    --xdivy;
    assert(xmody && ((y ^ xmody) >= 0));
}
*p_xdivy = xdivy;
*p_xmody = xmody;
return DIVMOD_OK;
}

- Eloff

---

divmod函数只执行一次操作吗？这个函数背后的代码是什么？ - BrunoLM

抢我说的了。divmod()是Python中的内置函数。 - Russell Borogove

@BrunoLM：虚拟机调用本地函数，我希望它执行本地的div指令。 - Russell Borogove

Python有符号整数除法是否总是给出正余数？与C和x86汇编的div不同，其中余数可以是负余数。因此，即使Python整数是单个“块”（而不是大数），它肯定不能只使用x86 div。这就是为什么C实现使用/但不使用%的原因。 - Peter Cordes

CRuby实现的divmod：return rb_assoc_new(num_div(x, y), num_modulo(x, y)); - Simon Perepelitsa

Answer 3

在C#/.NET中，你可以使用Math.DivRem函数： http://msdn.microsoft.com/en-us/library/system.math.divrem.aspx。

但是根据这个问题讨论串，这不是什么很有效的优化方法。

- elmattic

Answer 4

在Java（自1.5版本以来），类BigDecimal具有操作divideAndRemainder，返回一个由2个元素组成的数组，其中包含除法的结果和余数。

BigDecimal bDecimal = ...
BigDecimal[] result = bDecimal.divideAndRemainder(new BigDecimal(60));

Java 17 Javadoc: https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/math/BigDecimal.html#divideAndRemainder(java.math.BigDecimal)

这是Java 17的Javadoc文档，其中介绍了BigDecimal类的divideAndRemainder方法。该方法可以将一个BigDecimal对象除以另一个BigDecimal对象，并返回商和余数的数组。如果需要在精确计算的情况下进行除法运算，可以使用此方法。详细信息请参见上面提供的链接。

- Iván

Answer 5

.NET框架有 Math.DivRem 函数：

int mod, div = Math.DivRem(11, 3, out mod);
// mod = 2, div = 3

尽管 DivRem 只是对以下内容的包装：

int div = x / y;
int mod = x % y;

我不知道抖动是否可以将这种事情优化为单个指令。

- LukeH

Answer 6

Common Lisp提供以下功能：http://www.lispworks.com/documentation/HyperSpec/Body/f_floorc.htm

- Pedro Rodrigues

Answer 7

如Stringer Bell所提到的，有一个名为DivRem的函数在.NET 3.5中未进行优化。

在.NET 4.0上它使用NGen。

我使用Math.DivRem测试的结果（debug; release = ~11000ms）

11863
11820
11881
11859
11854

我使用 MyDivRem 得到的结果（调试版; 发布版 = 约11000毫秒）

29177
29214
29472
29277
29196

该项目针对x86架构。

---

Math.DivRem 的使用示例

int mod1;
int div1 = Math.DivRem(4, 2, out mod1);

方法签名

DivRem(Int32, Int32, Int32&) : Int32
DivRem(Int64, Int64, Int64&) : Int64

.NET 4.0 代码

[TargetedPatchingOptOut("Performance critical to inline across NGen image boundaries")]
public static int DivRem(int a, int b, out int result)
{
    result = a % b;
    return (a / b);
}

.NET 4.0 IL

.custom instance void System.Runtime.TargetedPatchingOptOutAttribute::.ctor(string) = { string('Performance critical to inline across NGen image boundaries') }
.maxstack 8
L_0000: ldarg.2 
L_0001: ldarg.0 
L_0002: ldarg.1 
L_0003: rem 
L_0004: stind.i4 
L_0005: ldarg.0 
L_0006: ldarg.1 
L_0007: div 
L_0008: ret 

MSDN参考

- BrunoLM

---

这个答案有点误导，因为你看到的突出显示的时间表明在.Net 4.0中优化了Math.DivRem，但是正如您稍微注意到的，它实际上根本没有被优化。实际上，在我的测试中，对于所有版本的.Net，Math.DivRem()比单独使用朴素的div和mod操作略慢，换句话说，它根本没有被优化。 - Chris Moschini

这是因为这是基准测试调试模式，所以与调用已编译的库函数相比，您自己代码中的任何内容都会很糟糕。它确实提到“发布”时间大致相等，这才是最重要的。（但我认为在这种情况下，“优化”意味着“不比让编译器[CSE]（https://en.wikipedia.org/wiki/Common_subexpression_elimination）`x/y`和`x％y`在开放版本中更糟糕，在.NET3.5中实际上可能更糟糕？） - Peter Cordes

Answer 8

Haskell中既有divMod，也有quotRem。后者直接对应于机器指令（根据Integral operators quot vs. div），而divMod可能不是这样。

- Jon Wolski

Answer 9

    int result,rest;
    _asm
    {
        xor edx, edx // pone edx a cero; edx = 0
        mov eax, result// eax = 2AF0
        mov ecx, radix // ecx = 4
        div ecx
        mov val, eax
        mov rest, edx
    }

- Ernesto Alfonso

---

编译器已经可以进行这种优化。使用 MSVC 的笨拙的内联汇编只会强制进行一些存储/重新加载往返。此外，您正在执行无符号除法，因此变量应该是“unsigned”，而不是“int”。另外，永远不要为已知为2的幂次方（例如4）使用“div”。使用“shr”/“and”获取商和余数。 - Peter Cordes