Division with negative dividend, but rounded towards negative infinity?

Question

Consider the following code (in C++11):

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

C++11 specification says that division with a negative dividend is rounded toward zero.

It is quite useful for there to be a operator or function to do division with rounding toward negative infinity (e.g. for consistency with positive dividends when iterating a range), so is there a function or operator in the standard library that does what I want? Or perhaps a compiler-defined function/intrinsic that does it in modern compilers?

I could write my own, such as the following (works only for positive divisors):

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

But it would not be as descriptive of my intent, and possibly not be as optimized a standard library function or compiler intrinsic (if it exists).

That's a simple error in the question. `-11 / 3 == -3`, `-11 % 3 == -2`. The question asks to divide in a way that makes `-11 / 3 == -4` (and `-11 % 3` would be `1`) — , Sep 03 '16 at 08:13
*"C++11 specification says that division with a negative dividend is rounded toward zero."* Positive dividends behave in different way? Probably I didn't get the question — BiagioF, Sep 03 '16 at 08:21
@BiagioFesta As of C++11, division is always rounded towards zero, for both positive and negative values. Prior to C++11, division was allowed to round to negative infinity, which is equivalent to rounding towards zero for positive values, but not so for negative ones. — , Sep 03 '16 at 08:25
Your function is wrong. `div_neg(-12, -3) == 2`; should obviously return `4`. — Tomek Sowiński, Sep 03 '16 at 09:11
@TomekSowiński I was only concerned about the case where the divisor is positive, but I wasn't clear about it in my question. I'll probably go with your solution. — Bernard, Sep 03 '16 at 12:58
Beware of overflow resulting in undefined behaviour in the `dividend - divisor` step. `(dividend + 1) / divisor - 1` would be safer than `(dividend - divisor + 1) / divisor`. — Mark Dickinson, Sep 03 '16 at 15:29

Tomek Sowiński · Accepted Answer · 2016-09-03T08:50:36.023

9

I'm not aware of any intrinsics for it. I would simply apply a correction to standard division retrospectively.

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;
}

Note it also works for pre-C99 and pre-C++11, i.e. without standarization of rounding division towards zero.

edited Sep 03 '16 at 08:50

answered Sep 03 '16 at 08:38

Tomek Sowiński

863
5
16

I'm getting confused by negative `b` values, but it looks like I may have got that wrong in my answer. – Sep 03 '16 at 09:00
Replacing the division and modulo with [`std::div`](http://www.cplusplus.com/reference/cstdlib/div/) from `` might give better performance. But then again maybe the compiler should be smart enough to notice. – Bernard Sep 03 '16 at 13:00
@Bernard Most probably. The remainder is a by-product of division on many architectures. Inspecting the disassembly wouldn't hurt, though. – Tomek Sowiński Sep 03 '16 at 15:38

Mark Dickinson · Answer 2 · 2016-09-03T18:59:04.767

Here's another possible variant, valid for positive divisors and arbitrary dividends.

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

Explanation: in the case of negative n, write q for (-1 - n) / d, then -1 - n = qd + r for some r satisfying 0 <= r < d. Rearranging gives n = (-1 - q)d + (d - 1 - r). It's clear that 0 <= d - 1 - r < d, so d - 1 - r is the remainder of the floor division operation, and -1 - q is the quotient.

Note that the arithmetic operations here are all safe from overflow, regardless of the internal representation of signed integers (two's complement, ones' complement, sign-magnitude).

Assuming two's complement representation for signed integers, a good compiler should optimise the two -1-* operations to bitwise negation operations. On my x86-64 machine, the second branch of the conditional gets compiled to the following sequence:

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

I particularly like this solution. `n >= 0 ? n / d : ~(~n / d)` is so symmetrical that it's beautiful. — Bernard, Sep 04 '16 at 02:32

score 2 · Answer 3 · 2016-09-03T09:04:54.193

2

The standard library has only one function that can be used to do what you want: floor. The division you're after can be expressed as floor((double) n / d). However, this assumes that double has enough precision to represent both n and d exactly. If not, then this may introduce rounding errors.

Personally, I'd go with a custom implementation. But you can use the floating point version too, if that's easier to read and you've verified that the results are correct for the ranges you're calling it for.

edited Sep 03 '16 at 09:04

answered Sep 03 '16 at 08:35

This is incorrect. floor(1.9) == 1 which is not rounding. – shirleyquirk Nov 26 '22 at 13:15

score 2 · Answer 4 · answered Sep 03 '16 at 14:45

C++11 has a std::div(a, b) that returns both a % b and a / b in struct with rem and quot members (so both remainder and quotient primitives) and for which modern processors have a single instruction. C++11 does truncated division.

To do floored division for both the remainder and the quotient, you can write:

// 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};
}

Finally, it's handy to also have Euclidean division (for which the remainder is always non-negative) in your own library:

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};
}

There is a Microsoft research paper discussing the pros and cons of the 3 versions.

score 0 · Answer 5 · answered May 20 '18 at 16:28

When the operands are both positive, the / operator does floored division.

When the operands are both negative, the / operator does floored division.

When exactly one of the operands is negative, the / operator does ceiling division.

For the last case, the quotient can be adjusted when exactly one operand is negative and there is no remainder (with no remainder, floored division and ceiling division work the same).

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;
}

Division with negative dividend, but rounded towards negative infinity?

5 Answers5