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 の答えintは同じなので、すべてを s にしています。 every と for every を置き換える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))。

于 2012-05-04T23:12:32.037 に答える
6

n のビット単位の補数n < 0をd > 0取り、除算を行い、結果のビット単位の補数を取得します。

int ifloordiv(int n, int d)
{
    if (n >= 0)
        return n / d;
    else
        return ~(~n / d);
}

For the remainder, a similar construction works (compatible with ifloordiv in the sense that the usual invariant ifloordiv(n, d) * d + ifloormod(n, d) == n is satisfied) giving a result that's always in the range [0, d).

int ifloormod(int n, int d)
{
    if (n >= 0)
        return n % d;
    else
        return d + ~(~n % d);
}

For negative divisors, the formulas aren't quite so neat. Here are expanded versions of ifloordiv and ifloormod that follow your 'nice-to-have' behavior option (b) for negative divisors.

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;
}

For d < 0, there's an unavoidable problem case when d == -1 and n is Integer.MIN_VALUE, since then the mathematical result overflows the type. In that case, the formula above returns the wrapped result, just as the usual Java division does. As far as I'm aware, this is the only corner case where we silently get 'wrong' results.

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