Problem
I want to make sure that if a division of integers is necessary, it is always rounded up. Is there a more effective method? There’s a lot of casting going on at the moment. 🙂
(int)Math.Ceiling((double)myInt1 / myInt2)
Asked by Karsten
Solution #1
UPDATE: In January 2013, I wrote a blog post about this topic. Thank you for asking such a fantastic question!
It’s difficult to get integer arithmetic right. As has been proved numerous times, the moment you attempt a “smart” trick, you are almost certain to make a mistake. When a fault is discovered, modifying the code to repair it without considering whether the fix may break something else is not an effective problem-solving strategy. So far, I believe five distinct incorrect integer arithmetic answers to this perfectly uncomplicated topic have been given.
The appropriate method to tackle integer arithmetic issues — that is, the technique that enhances the chances of obtaining the solution right the first time — is to take your time, solve the problem one step at a time, and apply excellent engineering concepts.
Begin by reading the manufacturer’s specifications for the item you’re seeking to replace. The integer division definition plainly states:
We need an integer division function that computes the quotient but always rounds the result upwards, not towards zero.
So, for that function, construct a specification. Every conceivable input must have behavior defined for our function int DivRoundUp(int dividend, int divisor). That unexplained behavior is really concerning, so let’s get rid of it. We’ll state that our operation meets the following criteria:
Now that we have a specification, we can confidently create a testable design. Since the “double” solution has been clearly rejected in the problem statement, let’s add an extra design constraint that the problem be addressed only with integer arithmetic, rather than computing the quotient as a double.
So, what do we need to compute? Clearly, we need to know three facts to match our standard while remaining purely in integer arithmetic. What was the integer quotient, first and foremost? Second, was there no remnant in the division? Was the integer quotient done by rounding up or down, if not?
We can begin developing code now that we have a specification and a design.
public static int DivRoundUp(int dividend, int divisor)
{
if (divisor == 0 ) throw ...
if (divisor == -1 && dividend == Int32.MinValue) throw ...
int roundedTowardsZeroQuotient = dividend / divisor;
bool dividedEvenly = (dividend % divisor) == 0;
if (dividedEvenly)
return roundedTowardsZeroQuotient;
// At this point we know that divisor was not zero
// (because we would have thrown) and we know that
// dividend was not zero (because there would have been no remainder)
// Therefore both are non-zero. Either they are of the same sign,
// or opposite signs. If they're of opposite sign then we rounded
// UP towards zero so we're done. If they're of the same sign then
// we rounded DOWN towards zero, so we need to add one.
bool wasRoundedDown = ((divisor > 0) == (dividend > 0));
if (wasRoundedDown)
return roundedTowardsZeroQuotient + 1;
else
return roundedTowardsZeroQuotient;
}
Is this ingenious? No. Is it lovely? No. Is it short? No. Is this correct in terms of the specifications? I think so, but I haven’t put it to the test. However, it appears to be quite nice.
We’re engineers, so follow excellent engineering principles. Investigate your tools, define the intended behavior, think about the worst-case scenarios first, and design the code in a way that emphasizes its evident correctness. And if you identify a bug, think about whether your algorithm is severely faulty to begin with before you start randomly flipping comparison directions and breaking things that already work.
Answered by Eric Lippert
Solution #2
So far, all of the responses appear to be overly complex.
You only need to do the following in C# and Java to get a positive dividend and divisor:
( dividend + divisor - 1 ) / divisor
Roland Backhouse, Number Conversion, 2001.
Answered by Ian Nelson
Solution #3
For signed integers:
int div = a / b;
if (((a ^ b) >= 0) && (a % b != 0))
div++;
For unsigned integers:
int div = a / b;
if (a % b != 0)
div++;
The integer division symbol ‘/’ is supposed to round to zero (7.7.2 of the specification), however we want to round up. Negative responses are already rounded correctly, but positive responses must be corrected.
Positive replies with a non-zero value are easy to spot, whereas answer zero might be either a rounding up of a negative number or a rounding down of a positive value.
The safest bet is to check that the signs of both integers are the same when the answer should be positive. When using the integer xor operator ” on the two numbers, the result will be a non-negative result with a 0 sign-bit, therefore the check (a b) >= 0 determines that the result should have been positive before rounding. Also, because every answer is obviously affirmative for unsigned integers, this check can be skipped.
The only thing left to check is whether any rounding has occurred, in which case a percent b!= 0 will suffice.
Arithmetic (both integer and non-integer) isn’t as straightforward as it appears. At all times, careful consideration is essential.
Also, while my final answer isn’t as’simple’, ‘obvious,’ or even ‘quick’ as the floating point answers, it does have one very strong redeeming quality for me: I’ve now reasoned through the answer, so I’m actually certain it’s correct (until someone smarter tells me otherwise -furtive glance in Eric’s direction-).
To get the same sense of certainty about the floating point answer, I’d have to do more (and possibly more complicated) thinking about whether there are any circumstances in which the floating-point precision might get in the way, and whether Math.Ceiling does anything untoward on ‘just the right’ inputs.
Replace (notice that I replaced the second myInt1 with myInt2, presuming you meant that):
(int)Math.Ceiling((double)myInt1 / myInt2)
with:
(myInt1 - 1 + myInt2) / myInt2
The only drawback is that you might not receive what you expect if myInt1 – 1 + myInt2 overflows the integer type you’re using.
This is incorrect for the following reasons: -1000000 and 3999 should equal -250, however it actually equals -249.
EDIT: Given that this produces the same problem as the other integer approach for negative myInt1 values, it might be simpler to write:
int rem;
int div = Math.DivRem(myInt1, myInt2, out rem);
if (rem > 0)
div++;
Using solely integer operations, this should yield the right value in div.
This is incorrect for the following reasons: The result of -1 and -5 should be 1, but it is 0 instead.
EDIT (again, with feeling): The division operator rounds to zero; this is correct for negative results, therefore only non-negative results require correction. Also, since DivRem only does a / and a percent, let’s skip the call (and start with the simple comparison to prevent modulo calculations when they aren’t required):
int div = myInt1 / myInt2;
if ((div >= 0) && (myInt1 % myInt2 != 0))
div++;
This is incorrect for the following reasons: -1 and 5 should equal 0; nevertheless, this results in 1.
(In my defense, I should never have attempted a reasoned answer while my mind was telling me I was 2 hours late for sleep on the last attempt.)
Answered by jerryjvl
Solution #4
This is a great opportunity to employ an extension method:
public static class Int32Methods
{
public static int DivideByAndRoundUp(this int number, int divideBy)
{
return (int)Math.Ceiling((float)number / (float)divideBy);
}
}
This improves the readability of your code as well:
int result = myInt.DivideByAndRoundUp(4);
Answered by joshcomley
Solution #5
You could create a supporter.
static int DivideRoundUp(int p1, int p2) {
return (int)Math.Ceiling((double)p1 / p2);
}
Answered by JaredPar
Post is based on https://stackoverflow.com/questions/921180/how-can-i-ensure-that-a-division-of-integers-is-always-rounded-up