Integer arithmetic is surprisingly difficult to get right. There are usually lots of weird corner cases,¹ and the temptation to use too-clever bit-twiddling tricks is high. Today I thought I'd give an example of how I approach solving integer arithmetic problems on those rare occasions when I have to. So let's consider the problem of writing a C# method that divides two 32 bit integers such that the division rounds up if it is inexact.

Before creating a new kind of division, it is instructive to consider what the existing integer division operator does. Obviously it divides a dividend by a divisor and produces a quotient, but there are some corner cases. The most obvious corner case is when the divisor is zero. Less obvious is the case where the dividend is Int32.MinValue and the divisor is -1. The correct answer mathematically is one greater than Int32.MaxValue. And as I discussed in 2011, it's not immediately clear whether -5 divided by 2 should have a quotient of -3 and a remainder of 1 or a quotient of -2 and a remainder of -1. Opinions vary.

The C# specification is mostly clear on all of these points. Summing up:

• Division by zero results in an exception.
• Division of Int32.MinValue by -1 either results in Int32.MinValue or an exception, at the discretion of the implementor.
• If the divisor and dividend have the same sign then the result is zero or positive.
• If the divisor and dividend have opposite signs then the result is zero or negative.
• If the division is inexact then the quotient is rounded towards zero. That is, up if it is negative, and down if it is positive.

Now let's use this as a model for our new method. That "implementation defined" point in there is a bit vexing, so let's eliminate it. Our proposed method should have the following behaviour:

• Division by zero results in an exception.
• Division of Int32.MinValue by -1 results in an exception.
• If the divisor and dividend have the same sign then the result is zero or positive.
• If the divisor and dividend have opposite signs then the result is zero or negative.
• If the division is inexact then the quotient is rounded up.

And now we have a specification from which we can write completely straightforward, boring code. Our implementation strategy will take advantage of the fact that the built-in operator does the heavy lifting; it already gives the desired result in the majority of cases, and only needs a small fixup in the few cases where it does not round up.

So when does regular division need to be fixed up? When the division is both inexact and rounded down. We can tell if the division was inexact if the remainder operator produces a non-zero result. But how can we tell if the division was rounded down?

We round towards zero, so the division was rounded down if the exact mathematical quotient was a positive fraction, and it was a positive fraction if the divisor and dividend were of the same sign. This is the point where people mess up. There is an easy way to determine if two numbers are of the same sign, and that's to compare their signs. The moment you depart from that, you get into trouble. In particular, multiplying two 32 bit integers together and checking to see if the result is positive does not tell you that the two integers were of the same sign! Integer arithmetic overflows; if it throws an exception in a checked context then obviously you do not know whether the two numbers were of the same sign. If it overflows in an unchecked context then two positive multiplicands can produce a negative product. Don't get cute; if you want to check if two things are the same then compare them for equality.

Enough chit-chat; let's write some code.

public static int DivRoundUp(int dividend, int divisor)
{
  if (divisor == 0 ) 
    throw new DivideByZeroException();
  if (divisor == -1 && dividend == Int32.MinValue) 
    throw new OverflowException();
  int roundedTowardsZeroQuotient = dividend / divisor;
  bool dividedEvenly = (dividend % divisor) == 0;
  if (dividedEvenly) 
    return roundedTowardsZeroQuotient;

At this point we know that the divisor was not zero (because we would have thrown) and we know that the 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 rounding towards zero rounded up, so we're done. If they're of the same sign then rounding towards zero rounded down, so we must add one to the quotient.

We compare signs by comparing signs:

  bool wasRoundedDown = ((divisor > 0) == (dividend > 0));
  if (wasRoundedDown) 
    return roundedTowardsZeroQuotient + 1;
  else
    return roundedTowardsZeroQuotient;
}

Now, is this the shortest way to write this code? No. Is it the fastest? No. Is it the cleverest? Certainly not. But it is clear, logical, follows the structure of its specification closely, and therefore more likely to be correct than shorter, faster, cleverer code. This variation has fewer tokens, and is considerably more clever:

  bool wasRoundedDown = (divisor ^ dividend) >= 0; 

It also trades two comparisons for one xor and therefore might be a few nanoseconds faster; I don't know. If this method turned out to be a bottleneck then you could experiment and find out. But I do know that the less clever version is a lot easier to read.