Round division of unsigned integers with no overflow

Question

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.

Comments are not for extended discussion; this conversation has been moved to chat. — Samuel Liew
– Samuel Liew, Commented Jun 22, 2020 at 3:11

Eric Postpischil · Accepted Answer · 2020-06-21 17:13:54Z

2

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

answered Jun 21, 2020 at 17:13

Eric Postpischil

233k15 gold badges199 silver badges379 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

goodvibration Over a year ago

May I suggest return n/d + n%d / (d-d/2), with no branching (boolean decision)?

Adrian Mole Over a year ago

@goodvibration But your suggestion has an extra division operation in place of a comparison; I would think the latter is faster.

goodvibration Over a year ago

@AdrianMole: That's platform-dependent. I'll leave it here for any future reader to decide (assuming it's correct).

Weather Vane Over a year ago

The n%d is probably a "free" side-effect of the division.d/2 will be done with a shift, which is cheap.

Adrian Mole Over a year ago

Maybe a decent compiler would not need branching. After the <= comparison, just add the NOT of the sign flag?

Weather Vane · Accepted Answer · 2020-06-21 17:11:26Z

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.

Collectives™ on Stack Overflow

Round division of unsigned integers with no overflow

Update

2 Answers 2

5 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

Update

2 Answers 2

5 Comments

Comments

Related