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

12

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

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

<code>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 */
}
</code>

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

вd < 0 Я думаю, у вас есть пара перевернутых знаков. Похоже, вы хотите0 <= r < -d для варианта (а) иd < r <= 0 для варианта (б). Mark Dickinson
правильно: спасибо, я имел в виду положительную версию делителя. (и оно должно было округляться до + бесконечности) Jason S
этотhas быть дубликатом, но я не могу его найти, и если он не является дубликатом, то я просто удивлен, что он еще не появился после 3+ лет StackOverflow. Jason S

Ваш Ответ

4   ответа
6

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 которые следуют за вашими "хорошими, чтобы иметь" Вариант поведения (б) для отрицательных делителей.

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. Насколько мне известно, это единственный угловой случай, когда мы молчаливо ошибаемся. Результаты.

Да, теперь это совершенно ясно.
@trutheality: правда, за исключением того, что результат по-прежнему получается как MIN_VALUE, что математически неверно (но корректно по модулю 2 ** & lt; независимо от & gt ;, так что, возможно, это достаточно хорошо). У меня неприятное ощущение, что есть другие угловые случаи, скрывающиеся заd < 0, но не нашли время, чтобы выяснить, что они все. Может быть, я должен сделать это.
@trutheality: я редактировал последний абзац; лучше? Насколько я могу судить, этот случай действительно является единственным угловым случаем.
@trutheality: Гах, я идиот! Спасибо; исправит это немедленно!
Оказывается, я не знал, что разделение может фактически переполниться.
6

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

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

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

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

Optimized answer:

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 Режим округления также вариант.)

New edit: Сейчас я просто пытаюсь понять, насколько далеко это можно оптимизировать для развлечения. С помощьюОтметить ответ лучшее, что у меня есть, это:

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

Я выхожу через дверь через минуту, но если я смогу проверить ее в понедельник на правильность, я +1 +1. Спасибо + хороших выходных .... Jason S
@ JasonS это XOR (^) не*.
Эд: Осторожно: n * d может дать неправильные результаты при переполнении. Jason S
Ницца! Тривиальная запутывающая оптимизация: заменить(n<0) ^ (d<0) сn^d < 0 , Компиляторmight сделать эту оптимизацию для вас, но я сомневаюсь в этом.
Пожалуйста, не направляйте меня к Math.floor. Если это произойдет, чтобы правильно работать дляint переменных (в которых я не уверен), он не будет работать дляlong переменные из-за отсутствия точности. Jason S
8

гуайява имеет это:IntMath.divide(int, int, RoundingMode.FLOOR) а такжеLongMath.divide(int, int, RoundingMode.FLOOR), (Раскрытие: я помогаю гуаве.)

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

@voipp: что бы вы с этим сделали? Как бы это отличалось от обычного двойного деления?
Почему в Гуаве нет функции деления для двойников?
Ничего такого. Вы, очевидно, правы
это приятно слышать - гуава очень уважаемая библиотека. Jason S
1
return BigDecimal.valueOf(n).divide(BigDecimal.valueOf(d), RoundingMode.FLOOR).longValue();

Похожие вопросы