Java: Как выполнить целочисленное деление, которое округляется к -Infinity, а не 0?

( note: не то же самое, что этот другой вопрос, поскольку OP никогда явно не указывал округление в сторону 0 или -Infinity)

JLS 15.17.2 говорит, что целочисленное деление округляется к нулю. Если я хочу floor() -подобное поведение для положительных делителей (меня не волнует поведение для отрицательных делителей), что простейший способ достичь этого, который является численным правилом для всех входов?

int ifloor(int n, int d)
{
    /* returns q such that n = d*q + r where 0 <= r < d
     * for all integer n, d where d > 0
     *
     * d = 0 should have the same behavior as `n/d`
     *
     * nice-to-have behaviors for d < 0:
     *   option (a). same as above: 
     *     returns q such that n = d*q + r where 0 <= r < -d
     *   option (b). rounds towards +infinity:
     *     returns q such that n = d*q + r where d < r <= 0
     */
}

long lfloor(long n, long d)
{
    /* same behavior as ifloor, except for long integers */
}

(обновление: я хочу иметь решение как для int, так и long арифметики.)

Ответ 1

Если вы можете использовать сторонние библиотеки, Guava имеет следующее: IntMath.divide(int, int, RoundingMode.FLOOR) и LongMath.divide(int, int, RoundingMode.FLOOR). (Раскрытие информации: Я вношу свой вклад в Гуаву.)

Если вы не хотите использовать стороннюю библиотеку для этого, вы все равно можете посмотреть на реализацию.

Ответ 2

(я делаю все для long, так как ответ для int тот же, просто замените int для каждого long и Integer для каждого long.)

Вы можете просто Math.floor результат двойного деления, иначе...

Оригинальный ответ:

return n/d - ( ( n % d != 0 ) && ( (n<0) ^ (d<0) ) ? 1 : 0 );

Оптимизированный ответ:

public static long lfloordiv( long n, long d ) {

    long q = n/d;
    if( q*d == n ) return q;
    return q - ((n^d) >>> (Long.SIZE-1));
}

(Для полноты, использование режима BigDecimal с ROUND_FLOOR округлением также является опцией.)

Новое редактирование: Теперь я просто пытаюсь понять, насколько он может быть оптимизирован для удовольствия. Используя Отметьте ответ, лучшее, что у меня есть до сих пор:

public static long lfloordiv2( long n, long d ){

    if( d >= 0 ){
        n = -n;
        d = -d;
    }
    long tweak = (n >>> (Long.SIZE-1) ) - 1;
    return (n + tweak) / d + tweak;
}

(Использует более дешевые операции, чем выше, но немного более длинный байт-код (29 против 26)).

Ответ 3

Здесь есть довольно аккуратная формула, которая работает, когда n < 0 и d > 0: возьмите поразрядное дополнение к n, выполните деление и затем побитовое дополнение к результату.

int ifloordiv(int n, int d)
{
    if (n >= 0)
        return n / d;
    else
        return ~(~n / d);
}

В остальном аналогичная конструкция работает (совместима с ifloordiv в том смысле, что выполняется обычный инвариант ifloordiv(n, d) * d + ifloormod(n, d) == n), давая результат всегда в диапазоне [0, d).

int ifloormod(int n, int d)
{
    if (n >= 0)
        return n % d;
    else
        return d + ~(~n % d);
}

Для отрицательных делителей формулы не совсем такие аккуратные. Ниже приведены расширенные версии ifloordiv и ifloormod, которые следуют вашему варианту поведения "nice-to-have" (b) для отрицательных делителей.

int ifloordiv(int n, int d)
{
    if (d >= 0)
        return n >= 0 ? n / d : ~(~n / d);
    else
        return n <= 0 ? n / d : (n - 1) / d - 1;
}

int ifloormod(int n, int d)
{
    if (d >= 0)
        return n >= 0 ? n % d : d + ~(~n % d);
    else
        return n <= 0 ? n % d : d + 1 + (n - 1) % d;
}

Для d < 0 существует неизбежный проблемный случай, когда d == -1 и n есть Integer.MIN_VALUE, так как тогда математический результат переполняет тип. В этом случае приведенная выше формула возвращает завернутый результат, как это делает обычное разделение Java. Насколько мне известно, это единственный угловой случай, когда мы молча получаем "неправильные" результаты.

Ответ 4

return BigDecimal.valueOf(n).divide(BigDecimal.valueOf(d), RoundingMode.FLOOR).longValue();