Integer Division Rounding with Negatives in C++

Integer division rounding with negatives in C++

According to the May 2008 revision,

You're right:

The binary / operator yields the quotient, and the binary % operator yields the remainder from the division of the first expression by the second. If the second operand of / or % is zero the behavior is undefined; otherwise (a/b)*b + a%b is equal to a. If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined75).

Note 75 says:

According to work underway toward the revision of ISO C, the preferred algorithm for integer division follows the rules defined in the ISO Fortran standard, ISO/IEC 1539:1991, in which the quotient is always rounded toward zero.

Chances are that C++ will lag C in this respect. As it stands, it's undefined but they have an eye towards changing it.

I work in the same department as Stroustrup and with a member of the committee. Things take AGES to get accomplished, and its endlessly political. If it seems silly, it probably is.

How to integer-divide round negative numbers *down*?

Note: this post produces incorrect results for input with a=-1. Please see other answers.

---

[c++]

This is probably what you meant by 'kludgey', but it's what I came up with.

int divideDown(int a, int b){
    int r=a/b;
    if (r<0 && r*b!=a)
        return r-1;
    return r;
}

In the if statement, I put r<0 - however I'm not sure if that's what you want. You may wish to change the if statement to

if (a<0 && b>0)

which would be consistent with your description "Seems like whenever I divide a negative int by a positive int ".

Integer division rounding down in C# (for negatives)

Dividing by 2 is a simple bitwise right-shift. After @elgonzo's (now deleted) mention of the properties of C#'s rightshift, I decided to have a look how it works, and it seems to do exactly what you want:

var result = number >> 1;

This gives the following results:

11 -> 5

10 -> 5

2 -> 1

1 -> 0

-1 -> -1

-2 -> -1

-32 -> -16

-33 -> -17

int.MaxValue and MinValue also work.

Performance-wise, this seems to be almost twice as fast as the currently accepted answer that uses modulo operators.
Dividing (the same) 100000000 random numbers costs 2.17 seconds on my machine using a simple shift, while using the version with modulo's takes between 3.1 and 4.0 seconds.

The branched versions seem to perform just about the same as the modulo version: significantly slower than the simple rightshift.

Rounding integer division (instead of truncating)

int a = 59.0f / 4.0f + 0.5f;

This only works when assigning to an int as it discards anything after the '.'

Edit:
This solution will only work in the simplest of cases. A more robust solution would be:

unsigned int round_closest(unsigned int dividend, unsigned int divisor)
{
    return (dividend + (divisor / 2)) / divisor;
}

What is the behavior of integer division?

Will result always be the floor of the division? What is the defined behavior?

Not quite. It rounds toward 0, rather than flooring.

6.5.5 Multiplicative operators

6 When integers are divided, the result of the / operator is the algebraic quotient with any
fractional part discarded.⁸⁸⁾ If the quotient a/b is representable, the expression
(a/b)*b + a%b shall equal a.

and the corresponding footnote:

88. This is often called ‘‘truncation toward zero’’.

Of course two points to note are:

3 The usual arithmetic conversions are performed on the operands.

and:

5 The result of the / operator is the
quotient from the division of the
first operand by the second; the
result of the % operator is the
remainder. In both operations, if the
value of the second operand is zero,
the behavior is undefined.

[Note: Emphasis mine]

Division with negative dividend, but rounded towards negative infinity?

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.

---

Related Topics