13

（注意：与其他问题不同，因为 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算术都有一个解决方案。）

4

4 回答 4

8

如果你可以使用第三方库，Guava有这个：IntMath.divide(int, int, RoundingMode.FLOOR)和LongMath.divide(int, int, RoundingMode.FLOOR). （披露：我为 Guava 做出了贡献。）

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

于 2012-05-05T00:06:22.233 回答
7

（我正在为longs 做所有事情，因为 s 的答案int是相同的，只需替换inteverylong和Integerfor every 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舍入模式的 a 也是一种选择。）

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

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 vs. 26））。

于 2012-05-04T23:12:32.037 回答
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遵循负除数的“不错”行为选项 (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时，存在一个不可避免的问题情况，因为那时数学结果会溢出类型。在这种情况下，上面的公式会返回包装后的结果，就像通常的 Java 除法一样。据我所知，这是我们默默得到“错误”结果的唯一极端情况。d == -1nInteger.MIN_VALUE

于 2012-05-05T22:18:28.103 回答
1 
return BigDecimal.valueOf(n).divide(BigDecimal.valueOf(d), RoundingMode.FLOOR).longValue();
于 2012-05-07T18:43:33.270 回答