Java: Wie kann ich integer-division, die Runden in Richtung -Unendlich, anstatt 0?

(Hinweis: nicht das gleiche wie diese andere Frage seit der OP nie explizit angegeben Rundung in Richtung 0 oder -Unendlich)

JLS 15.17.2 sagt, dass die integer-division " rundet in Richtung null. Wenn ich will floor()-wie Verhalten für positive Teiler (I don ' T care über das Verhalten für negative Teiler), was ist der einfachste Weg, dies zu erreichen, die numerisch richtige für alle Eingänge?

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 */
}

(update: ich möchte eine Lösung, die sowohl für int und long Arithmetik.)

  • dies hat eine doppelte, aber ich kann es nicht finden, und wenn es nicht ein Duplikat ist, dann bin ich nur Total überrascht, dass es nicht kommen die noch nach 3+ Jahren von StackOverflow.
  • In der d < 0 Bedingungen für den Rest, ich glaube, du hast ein paar von inversen Zeichen. Es sieht aus wie Sie wollen 0 <= r < -d für option (a) und d < r <= 0 für option (b).
  • rechts: danke, ich habe meine, die positive version der divisor. (und es hätte Rundung in Richtung +unendlich)
InformationsquelleAutor Jason S | 2012-05-04
  1. 8

    Wenn Sie können Bibliotheken von Drittanbietern verwenden, Guave hat diese: IntMath.divide(int, int RoundingMode.ETAGE) und LongMath.divide(int, int RoundingMode.ETAGE). (Disclosure: ich trage zu Guave.)

    Wenn Sie nicht möchten, verwenden Sie ein Drittanbieter-Bibliothek für diese, können Sie sehen immer noch an der Umsetzung.

    • das ist gut zu hören-Guave ist eine sehr seriöse Bibliothek.
    • Warum nicht Guave enthalten division-Funktion für Doppel ?
    • was würden Sie selbst tun? Wie wäre es unterscheiden sich von normalen Doppel-division?
    • Nichts. Sie sind offensichtlich richtig
    InformationsquelleAutor Louis Wasserman
  2. 6

    Gibt es eine ziemlich nette Formel für das, dass funktioniert, wenn n < 0 und d > 0: nehmen Sie das bitweise Komplement von n, tun die division, und dann nehmen Sie das bitweise Komplement des Ergebnisses.

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

    Für den Rest, eine ähnliche Konstruktion funktioniert (kompatibel mit ifloordiv in dem Sinne, dass die üblichen invariante ifloordiv(n, d) * d + ifloormod(n, d) == n zufrieden ist) was eine Folge immer im Bereich [0, d).

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

    Negativen Teiler, die Formeln sind nicht ganz so sauber. Hier sind erweiterte Versionen von ifloordiv und ifloormod Folgen, dass Ihr 'nice-to-have' - Verhalten option (b) für negative Teiler.

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

    Für d < 0 gibt es eine unvermeidbare problem Fall, wenn d == -1 und n ist Integer.MIN_VALUE, da dann das mathematische Ergebnis überläuft der Typ. In diesem Fall, die obige Formel gibt den umschlossenen Ergebnis, ebenso wie die üblichen Java-Teilung macht. So weit ich bin mir bewusst,, dies ist die einzige Ecke Fall, wo wir schweigend bekommen "falschen" Ergebnisse.

    • Gah, ich bin ein idiot! Danke; beheben Sie dies sofort!
    • Wahr, außer, dass das Ergebnis kommt immer noch als MIN_VALUE, das ist mathematisch falsch (aber korrekte modulo 2**<was auch immer>, so vielleicht ist das gut genug). Ich habe eine böse Gefühl, dass es anderen Ecke Fälle lauern für d < 0, aber haben nicht die Zeit nehmen, um herauszufinden, was Sie alle sind. Vielleicht sollte ich das tun.
    • Huh, stellt sich heraus, ich war nicht bewusst, dass die Teilung kann tatsächlich überlaufen.
    • Bearbeitet ich der Letzte Absatz; besser? So weit wie ich kann sagen, dass der Fall wirklich die einzige Ecke Fall.
    • Ja, das ist vollkommen klar.
    InformationsquelleAutor Mark Dickinson
  3. 6

    (Ich Tue alles für longs da die Antwort für ints ist die gleiche, nur Ersatz int für jeden long und Integer für jeden Long.)

    Konnte man nur Math.Boden eine double-division, Ergebnis, ansonsten...

    Original Antwort:

    return n/d - ( ( n % d != 0 ) && ( (n<0) ^ (d<0) ) ? 1 : 0 );

    Optimierte Antwort:

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

    (Der Vollständigkeit halber, mit einem BigDecimal mit einem ROUND_FLOOR Rundung-Modus ist auch eine option.)

    Neuer edit: Jetzt bin ich nur versucht, um zu sehen, wie weit optimiert werden können, zum Spaß. Mit Mark ' s Antwort die beste, die ich habe, so weit ist:

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

    (Verwendet billiger Operationen als die obige, aber etwas länger bytecode (29 vs. 26)).

    • Bitte nicht finden Sie mich auf dem Weg zur Mathematik.Boden. Wenn es passiert, um richtig zu arbeiten für int Variablen (von denen ich nicht sicher bin), ist es nicht für die Arbeit long Variablen, weil der Mangel an Präzision.
    • Ich bin Position aus der Tür, in einer minute, aber wenn ich die spot-check-es am Montag für die Richtigkeit, ich werde +1. Vielen Dank + ein schönes Wochenende....
    • Schön! Eine triviale Verschleierung Optimierung: ersetzen (n<0) ^ (d<0) mit n^d < 0 . Der compiler könnte tun, um diese Optimierung für Sie, aber ich bezweifle es.
    • Ed: Watch out: n*d kann zu unpassenden Ergebnisse auf überlauf.
    • das ist ein XOR (^) nicht *.
    • Die zweite Lösung ist falsch. Wenn n ist -3 und d ist 2 diese Funktion Ausgänge -1 (falsch).
    • schönen Fang, das ist, was ich für den Versuch, Mikro-Optimierung ohne testing...

    InformationsquelleAutor
  4. 1
    return BigDecimal.valueOf(n).divide(BigDecimal.valueOf(d), RoundingMode.FLOOR).longValue();
    InformationsquelleAutor jtahlborn
Schreibe einen Kommentar