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

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);

Answer 3

If both arguments a and b are long (or any other integer type)

long c = a/b;

is giving a floor integer division in C# just like in Python. Nothing to convert to anything. It is even using a proper integer operation on the processor level.

All operations in C# are executed based on their types.