Round division of unsigned integers with no overflow

user_7400903 0
Viewed 85

I'm looking for an overflow-safe method to perform round division of unsigned integers.

I have this:

uint roundDiv(uint n, uint d)
{
    return (n + d / 2) / d;
}

But unfortunately, the expression n + d / 2 may overflow.

I think that I will have to check whether or not n % d is smaller than d / 2.

But d / 2 itself may truncate (when d is odd).

So I figured I should check whether or not n % d * 2 is smaller than d.

Or even without a logical condition, rely on the fact that n % d * 2 / d is either 0 or 1:

uint roundDiv(uint n, uint d)
{
    return n / d + n % d * 2 / d;
}

This works well, however once again, n % d * 2 may overflow.

Is there any custom way to achieve round integer division which is overflow-safe?

Update

I have come up with this:

uint roundDiv(uint n, uint d)
{
    if (n % d < (d + d % 2) / 2)
        return n / d;
    return n / d + 1;
}

Still, the expression d + d % 2 may overflow.

integer-division rounding c
2 Answers

return n/d + (d-d/2 <= n%d);

user_2982250

The way to avoid overflow at any stage is, as OP stated, to compare the remainder with half the divisor, but the result isn't quite as obvious as it first seems. Here are some examples, with the assumption that 0.5 would round up. First with an odd divisor:

Numerator   Divisor Required    Quotient    Remainder   Half divisor    Quot < Req?
3           3       1           1           0           1               no
4           3       1           1           1           1               no
5           3       2           1           2           1               yes
6           3       2           2           0           1               no

Above, the only increment needed is when d / 2 < remainder. Now with an even divisor:

Numerator   Divisor Required    Quotient    Remainder   Half divisor    Quot < Req?
4           4       1           1           0           2               no
5           4       1           1           1           2               no
6           4       2           1           2           2               yes
7           4       2           1           3           2               yes
8           4       2           2           0           2               no

But here, the increment is needed when d / 2 <= remainder.

Summary:

  • You need a different condition depending on odd or even divisor.
user_41429240
Related