Java:如何执行向-Infinity而不是0舍入的整数除法？

Question

(注意:与其他问题不同,因为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算术.)

Answer 1

如果您可以使用第三方库,Guava就有:IntMath.divide(int, int, RoundingMode.FLOOR)和LongMath.divide(int, int, RoundingMode.FLOOR).(披露:我向番石榴捐款.)

如果您不想为此使用第三方库,您仍然可以查看实现.

Answer 2

(我正在为longs 做一切,因为s的答案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舍入模式的选项也是一种选择.)

新编辑:现在我只想看看它可以在多大程度上进行优化以获得乐趣.使用Mark的答案我到目前为止最好的是:

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

Answer 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遵循你的"好的"行为选项(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分区一样.据我所知,这是唯一一个我们默默得到"错误"结果的角落.