How can I ensure that a division of integers is always rounded up?

Question

UPDATE: This question was the subject of my blog in January 2013. Thanks for the great question!

---

Getting integer arithmetic correct is hard. As has been demonstrated amply thus far, the moment you try to do a "clever" trick, odds are good that you've made a mistake. And when a flaw is found, changing the code to fix the flaw without considering whether the fix breaks something else is not a good problem-solving technique. So far we've had I think five different incorrect integer arithmetic solutions to this completely not-particularly-difficult problem posted.

The right way to approach integer arithmetic problems -- that is, the way that increases the likelihood of getting the answer right the first time - is to approach the problem carefully, solve it one step at a time, and use good engineering principles in doing so.

Start by reading the specification for what you're trying to replace. The specification for integer division clearly states:

1. The division rounds the result towards zero

2. The result is zero or positive when the two operands have the same sign and zero or negative when the two operands have opposite signs

3. If the left operand is the smallest representable int and the right operand is –1, an overflow occurs. [...] it is implementation-defined as to whether [an ArithmeticException] is thrown or the overflow goes unreported with the resulting value being that of the left operand.

4. If the value of the right operand is zero, a System.DivideByZeroException is thrown.

What we want is an integer division function which computes the quotient but rounds the result always upwards, not always towards zero.

So write a specification for that function. Our function int DivRoundUp(int dividend, int divisor) must have behaviour defined for every possible input. That undefined behaviour is deeply worrying, so let's eliminate it. We'll say that our operation has this specification:

1. operation throws if divisor is zero

2. operation throws if dividend is int.minval and divisor is -1

3. if there is no remainder -- division is 'even' -- then the return value is the integral quotient

4. Otherwise it returns the smallest integer that is greater than the quotient, that is, it always rounds up.

Now we have a specification, so we know we can come up with a testable design. Suppose we add an additional design criterion that the problem be solved solely with integer arithmetic, rather than computing the quotient as a double, since the "double" solution has been explicitly rejected in the problem statement.

So what must we compute? Clearly, to meet our spec while remaining solely in integer arithmetic, we need to know three facts. First, what was the integer quotient? Second, was the division free of remainder? And third, if not, was the integer quotient computed by rounding up or down?

Now that we have a specification and a design, we can start writing code.

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 clever? No. Beautiful? No. Short? No. Correct according to the specification? I believe so, but I have not fully tested it. It looks pretty good though.

We're professionals here; use good engineering practices. Research your tools, specify the desired behaviour, consider error cases first, and write the code to emphasize its obvious correctness. And when you find a bug, consider whether your algorithm is deeply flawed to begin with before you just randomly start swapping the directions of comparisons around and break stuff that already works.

All the answers here so far seem rather over-complicated.

In C# and Java, for positive dividend and divisor, you simply need to do:

( dividend + divisor - 1 ) / divisor 

Source: Number Conversion, Roland Backhouse, 2001

The final int-based answer

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 reasoning for this answer

Integer division '/' is defined to round towards zero (7.7.2 of the spec), but we want to round up. This means that negative answers are already rounded correctly, but positive answers need to be adjusted.

Non-zero positive answers are easy to detect, but answer zero is a little trickier, since that can be either the rounding up of a negative value or the rounding down of a positive one.

The safest bet is to detect when the answer should be positive by checking that the signs of both integers are identical. Integer xor operator '^' on the two values will result in a 0 sign-bit when this is the case, meaning a non-negative result, so the check (a ^ b) >= 0 determines that the result should have been positive before rounding. Also note that for unsigned integers, every answer is obviously positive, so this check can be omitted.

The only check remaining is then whether any rounding has occurred, for which a % b != 0 will do the job.

Lessons learned

Arithmetic (integer or otherwise) isn't nearly as simple as it seems. Thinking carefully required at all times.

Also, although my final answer is perhaps not as 'simple' or 'obvious' or perhaps even 'fast' as the floating point answers, it has one very strong redeeming quality for me; I have now reasoned through the answer, so I am actually certain it is correct (until someone smarter tells me otherwise -furtive glance in Eric's direction-).

To get the same feeling of certainty about the floating point answer, I'd have to do more (and possibly more complicated) thinking about whether there is any conditions under which the floating-point precision might get in the way, and whether Math.Ceiling perhaps does something undesirable on 'just the right' inputs.

The path travelled

Replace (note I replaced the second myInt1 with myInt2, assuming that was what you meant):

(int)Math.Ceiling((double)myInt1 / myInt2)

with:

(myInt1 - 1 + myInt2) / myInt2

The only caveat being that if myInt1 - 1 + myInt2 overflows the integer type you are using, you might not get what you expect.

Reason this is wrong: -1000000 and 3999 should give -250, this gives -249

EDIT:
Considering this has the same error as the other integer solution for negative myInt1 values, it might be easier to do something like:

int rem;
int div = Math.DivRem(myInt1, myInt2, out rem);
if (rem > 0)
  div++;

That should give the correct result in div using only integer operations.

Reason this is wrong: -1 and -5 should give 1, this gives 0

EDIT (once more, with feeling):
The division operator rounds towards zero; for negative results this is exactly right, so only non-negative results need adjustment. Also considering that DivRem just does a / and a % anyway, let's skip the call (and start with the easy comparison to avoid modulo calculation when it is not needed):

int div = myInt1 / myInt2;
if ((div >= 0) && (myInt1 % myInt2 != 0))
    div++;

Reason this is wrong: -1 and 5 should give 0, this gives 1

(In my own defence of the last attempt I should never have attempted a reasoned answer while my mind was telling me I was 2 hours late for sleep)

Perfect chance to use 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 makes your code uber readable too:

int result = myInt.DivideByAndRoundUp(4);

You could write a helper.

static int DivideRoundUp(int p1, int p2) {
  return (int)Math.Ceiling((double)p1 / p2);
}