( 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 арифметики.)
Если вы можете использовать сторонние библиотеки, Guava имеет следующее: IntMath.divide(int, int, RoundingMode.FLOOR) и LongMath.divide(int, int, RoundingMode.FLOOR). (Раскрытие информации: Я вношу свой вклад в Гуаву.)
Если вы не хотите использовать стороннюю библиотеку для этого, вы все равно можете посмотреть на реализацию.
(я делаю все для 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)).
Здесь есть довольно аккуратная формула, которая работает, когда 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. Насколько мне известно, это единственный угловой случай, когда мы молча получаем "неправильные" результаты.
return BigDecimal.valueOf(n).divide(BigDecimal.valueOf(d), RoundingMode.FLOOR).longValue();