Floored integer division

Question

Is there an easy, efficient and correct (i.e. not involving conversions to/from double) way to do floored integer division (like e.g. Python offers) in C#.

In other words, an efficient version of the following, that does not suffer from long/double conversion losses.

(long)(Math.Floor((double) a / b))

or does one have to implement it oneself, like e.g.

static long FlooredIntDiv(long a, long b)
{
    if (a < 0)
    {
        if (b > 0)
            return (a - b + 1) / b;
        // if (a == long.MinValue && b == -1) // see *) below
        //    throw new OverflowException();
    }
    else if (a > 0)
    {
        if (b < 0)
            return (a - b - 1) / b;
    }
    return a / b;
}

*) Although the C# 4 spec of the Division operator leaves it open whether OverflowException is raised inside unchecked, in reality it does throw (on my system) and the Visual Studio .NET 2003 version even mandated it throw:

If the left operand is the smallest representable int or long value and the right operand is –1, [..] System.OverflowException is always thrown in this situation, regardless of whether the operation occurs in a checked or an unchecked context.

Edit

The crossed out statements about checked and unchecked are all nice and well, but checked is in fact only a compile time concept, so whether my function should wrap around or throw is up to me anyway, regardless of whether code calling the function is inside checked or not.

Answer 1

You can try this:

if (((a < 0) ^ (b < 0)) && (a % b != 0))
{
   return (a/b - 1);
}
else
{
   return (a/b);
}

Edit (after some discussions in comments below):

Without using if-else, I would go like this:

return (a/b - Convert.ToInt32(((a < 0) ^ (b < 0)) && (a % b != 0)));

Note: Convert.ToIn32(bool value) also needs a jump, see implemention of the method:

return value? Boolean.True: Boolean.False;

Theoretically, it is not possible to calculate the division for a = long.MinValue and b = -1L, since the expected result is a/b = abs(long.MinValue) = long.MaxValue + 1 > long.MaxValue. (Range of long is –9,223,372,036,854,775,808 to 9,223,372,036,854,775,807.)

Answer 2

The way it works in any sane programming language (one that follows our normal order of operations) is that -1.0/3.0 is equivalent to -(1.0/3.0) which is -0.3333.... So if you want that converted to an int, it's really the cast/floor operator you need to think about, not the division. As such, if you want this behavior, you must use (int)Math.Floor(a/b), or custom code.

Answer 3

You don't need to implement this yourself, the Math class provides a builtin method for doing Euclidean division: Math.DivRem()

The only downside is that you have to provide an assignable variable for the remainder:

long remainder;
long quotient = Math.DivRem(a, b, out remainder);