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

(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 арифметика.)

 Mark Dickinson06 мая 2012 г., 11:59
вd < 0 Я думаю, у вас есть пара перевернутых знаков. Похоже, вы хотите0 <= r < -d для варианта (а) иd < r <= 0 для варианта (б).
 Jason S06 мая 2012 г., 15:00
правильно: спасибо, я имел в виду положительную версию делителя. (и оно должно было округляться до + бесконечности)
 Jason S05 мая 2012 г., 01:09
этотhas быть дубликатом, но я не могу его найти, и если он не является дубликатом, то я просто удивлен, что он еще не появился после 3+ лет StackOverflow.

Ответы на вопрос(4)

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

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

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

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

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

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

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

Ваш ответ на вопрос