股息为负的除法，但四舍五入为负无穷大？

Question

考虑以下代码（C++11 中）：

int a = -11, b = 3;
int c = a / b;
// now c == -3

C++11 规范规定，除数为负的除法将四舍五入为零。

有一个运算符或函数来进行向负无穷大舍入的除法（例如，在迭代范围时与正股息保持一致）是非常有用的，那么标准库中是否有一个函数或运算符可以完成我想要的操作？ 或者也许是编译器定义的函数/内在函数在现代编译器中执行此操作？

我可以自己写，例如以下内容（仅适用于正除数）：

int div_neg(int dividend, int divisor){
    if(dividend >= 0) return dividend / divisor;
    else return (dividend - divisor + 1) / divisor;
}

但它不会描述我的意图，并且可能不会像标准库函数或编译器内在函数（如果存在）那样优化。

Answer 1

我不知道它有任何内在的东西。我会简单地回顾性地对标准除法进行修正。

int div_floor(int a, int b)
{
    int res = a / b;
    int rem = a % b;
    // Correct division result downwards if up-rounding happened,
    // (for non-zero remainder of sign different than the divisor).
    int corr = (rem != 0 && ((rem < 0) != (b < 0)));
    return res - corr;
}

请注意，它也适用于 C99 之前的版本和 C++11 之前的版本，即没有向零舍入除法的标准化。

Answer 2

这是另一种可能的变体，适用于正除数和任意股息。

int div_floor(int n, int d) {
    return n >= 0 ? n / d : -1 - (-1 - n) / d;
}

说明：在

n

为负的情况下，对于

q

写

(-1 - n) / d

，对于某些满足

-1 - n = qd + r

的

r

写

0 <= r < d

。重新排列得到

n = (-1 - q)d + (d - 1 - r)

。很明显，

0 <= d - 1 - r < d

，所以

d - 1 - r

是整除运算的余数，

-1 - q

是商。

请注意，假设有符号整数采用二进制补码表示（自 C23 起强制执行），则此处的算术运算都不会溢出。

再次假设有符号整数的补码表示，一个好的编译器应该将两个

-1-*

操作优化为按位求反操作。在我的 x86-64 机器上，条件的第二个分支被编译为以下序列：

notl    %edi
movl    %edi, %eax
cltd
idivl   %esi
notl    %eax

Answer 3

标准库只有一个函数可以用来做你想做的事情：

floor

。您所追求的除法可以表示为

floor((double) n / d)

。然而，这假设

double

有足够的精度来准确表示

n

和

d

。如果不是，那么这可能会引入舍入误差。

就我个人而言，我会选择自定义实现。但是您也可以使用浮点版本，如果这样更容易阅读并且您已经验证结果对于您调用的范围是正确的。

Answer 4

C++11 有一个

std::div(a, b)

，它在具有

a % b

和

a / b

成员的结构中返回

rem

和

quot

（因此余数和商基元），并且现代处理器对此有一条指令。 C++11 执行截断除法。

要对余数和商进行取整除法，您可以编写：

// http://stackoverflow.com/a/4609795/819272
auto signum(int n) noexcept
{
        return static_cast<int>(0 < n) - static_cast<int>(n < 0);
}

auto floored_div(int D, int d) // Throws: Nothing.
{
        assert(d != 0);

        auto const divT = std::div(D, d);
        auto const I = signum(divT.rem) == -signum(d) ? 1 : 0;
        auto const qF = divT.quot - I;
        auto const rF = divT.rem + I * d;

        assert(D == d * qF + rF);
        assert(abs(rF) < abs(d));
        assert(signum(rF) == signum(d));

        return std::div_t{qF, rF};
}

最后，在您自己的库中也可以方便地使用欧几里得除法（余数始终为非负）：

auto euclidean_div(int D, int d) // Throws: Nothing.
{
        assert(d != 0);

        auto const divT = std::div(D, d);
        auto const I = divT.rem >= 0 ? 0 : (d > 0 ? 1 : -1);
        auto const qE = divT.quot - I;
        auto const rE = divT.rem + I * d;

        assert(D == d * qE + rE);
        assert(abs(rE) < abs(d));
        assert(signum(rE) != -1);

        return std::div_t{qE, rE};
}

有微软研究论文讨论了3个版本的优缺点。

Answer 5

当操作数均为正数时，

/

运算符进行向下除法。

当操作数均为负数时，

/

运算符进行向下除法。

当恰好有一个操作数为负数时，

/

运算符进行上除法。

对于最后一种情况，当恰好有一个操作数为负并且没有余数时可以调整商（没有余数，下底除法和上限除法的工作原理相同）。

int floored_div(int numer, int denom) {
  int div = numer / denom;
  int n_negatives = (numer < 0) + (denom < 0);
  div -= (n_negatives == 1) && (numer % denom != 0);
  return div;
}