Separation with a negative dividend, but rounded to negative infinity?

Question

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

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

The C ++ 11 specification states that division with a negative dividend is rounded to zero.

It is very useful if there were an operator or function for dividing with rounding to negative infinity (for example, for consistency with positive dividends during range iteration), so is there a function or operator in the standard library that does what I want? Or perhaps a compiler-defined function / internal that does this in modern compilers?

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

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

But this would not be how to describe my intentions and, perhaps, not be optimized as a standard library function, but an inbuilt compiler (if it exists).

Answer 1

I do not know about that. I would just apply the fix to the standard tick marks 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 that it also works for pre-C99 and pre-C ++ 11, i.e. without standardizing rounding to zero.

Answer 2

The standard library has only one function that can be used to accomplish what you want: floor . The division you follow can be expressed as floor((double) n / d) . However, this suggests that double has sufficient precision to represent both n and d accurately. If not, then this can lead to rounding errors.

Personally, I would go with a custom implementation. But you can also use the floating point version if it is easier to read, and you have confirmed the results are correct for the ranges for which you call it.

Answer 3

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

To make a split in half 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 also convenient to have Euclidean separation (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}; } 

A Microsoft research paper discusses the pros and cons of three versions.

Answer 4

Here is another possible option, valid for positive dividers and arbitrary dividends.

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

Explanation: for negative n write q for (-1 - n) / d , then -1 - n = qd + r for some r satisfying 0 <= r < d . The permutation gives n = (-1 - q)d + (d - 1 - r) . It is clear that 0 <= d - 1 - r < d , therefore d - 1 - r is the remainder of the sex division operation, and -1 - q is the factor.

Please note that arithmetic operations here are safe from overflow, regardless of the internal representation of signed integers (two additions, their complement, sign-value).

Assuming two additional representations for signed integers, a good compiler should optimize two -1-* operations for bitwise negation operations. On my x86-64 machine, the second branch of the conditional code is compiled into the following sequence:

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