Wie kann ich sicherstellen, dass eine Division von ganzen Zahlen immer aufgerundet wird?

Ich möchte sicherstellen, dass eine Division von ganzen Zahlen bei Bedarf immer aufgerundet wird. Gibt es einen besseren Weg als diesen? Es wird viel gecastet. :-)

(int)Math.Ceiling((double)myInt1 / myInt2)

UPDATE: Diese Frage war das Thema meines Blogs im Januar 2013 . Danke für die tolle Frage!

Es ist schwierig, eine ganzzahlige Arithmetik richtig zu machen. Wie bisher ausführlich gezeigt wurde, stehen die Chancen gut, dass Sie einen Fehler gemacht haben, sobald Sie versuchen, einen "cleveren" Trick auszuführen. Und wenn ein Fehler gefunden wird, ist es keine gute Technik zur Problemlösung , den Code zu ändern, um den Fehler zu beheben, ohne zu berücksichtigen, ob der Fehler etwas anderes beschädigt. Bisher haben wir fünf verschiedene falsche ganzzahlige arithmetische Lösungen für dieses völlig nicht besonders schwierige Problem veröffentlicht.

Der richtige Weg, um ganzzahlige arithmetische Probleme anzugehen - das heißt, der Weg, der die Wahrscheinlichkeit erhöht, dass die Antwort beim ersten Mal richtig ist - besteht darin, sich dem Problem sorgfältig zu nähern, es Schritt für Schritt zu lösen und dabei gute technische Prinzipien anzuwenden so.

Lesen Sie zunächst die Spezifikation für das, was Sie ersetzen möchten. In der Spezifikation für die Ganzzahldivision heißt es eindeutig:

1. Die Division rundet das Ergebnis gegen Null

2. Das Ergebnis ist Null oder positiv, wenn die beiden Operanden das gleiche Vorzeichen haben, und Null oder negativ, wenn die beiden Operanden entgegengesetzte Vorzeichen haben

3. Wenn der linke Operand der kleinste darstellbare int ist und der rechte Operand –1 ist, tritt ein Überlauf auf. [...] es ist implementierungsdefiniert, ob [eine ArithmeticException] ausgelöst wird oder der Überlauf nicht gemeldet wird, wobei der resultierende Wert der des linken Operanden ist.

4. Wenn der Wert des rechten Operanden Null ist, wird eine System.DivideByZeroException ausgelöst.

Was wir wollen, ist eine ganzzahlige Divisionsfunktion, die den Quotienten berechnet, aber das Ergebnis immer nach oben rundet , nicht immer gegen Null .

Schreiben Sie also eine Spezifikation für diese Funktion. Für unsere Funktion int DivRoundUp(int dividend, int divisor)muss für jede mögliche Eingabe ein Verhalten definiert sein. Dieses undefinierte Verhalten ist zutiefst besorgniserregend, also lasst es uns beseitigen. Wir werden sagen, dass unser Betrieb diese Spezifikation hat:

1. Operation wird ausgelöst, wenn der Divisor Null ist

2. Operation wird ausgelöst, wenn die Dividende int.minval und der Divisor -1 ist

3. Wenn es keinen Rest gibt - Division ist 'gerade' -, ist der Rückgabewert der integrale Quotient

4. Andernfalls wird die kleinste Ganzzahl zurückgegeben, die größer als der Quotient ist, dh immer aufgerundet.

Jetzt haben wir eine Spezifikation, damit wir wissen, dass wir ein testbares Design entwickeln können . Angenommen, wir fügen ein zusätzliches Entwurfskriterium hinzu, dass das Problem ausschließlich mit ganzzahliger Arithmetik gelöst werden soll, anstatt den Quotienten als Doppel zu berechnen, da die "doppelte" Lösung in der Problemstellung explizit abgelehnt wurde.

Was müssen wir also berechnen? Um unsere Spezifikation zu erfüllen und dabei ausschließlich in der Ganzzahlarithmetik zu bleiben, müssen wir drei Fakten kennen. Was war der ganzzahlige Quotient? Zweitens war die Division frei von Rest? Und drittens, wenn nicht, wurde der ganzzahlige Quotient durch Auf- oder Abrunden berechnet?

Nachdem wir eine Spezifikation und ein Design haben, können wir mit dem Schreiben von Code beginnen.

public static int DivRoundUp(int dividend, int divisor)
{
  if (divisor == 0 ) throw ...
  if (divisor == -1 && dividend == Int32.MinValue) throw ...
  int roundedTowardsZeroQuotient = dividend / divisor;
  bool dividedEvenly = (dividend % divisor) == 0;
  if (dividedEvenly) 
    return roundedTowardsZeroQuotient;

  // At this point we know that divisor was not zero 
  // (because we would have thrown) and we know that 
  // dividend was not zero (because there would have been no remainder)
  // Therefore both are non-zero.  Either they are of the same sign, 
  // or opposite signs. If they're of opposite sign then we rounded 
  // UP towards zero so we're done. If they're of the same sign then 
  // we rounded DOWN towards zero, so we need to add one.

  bool wasRoundedDown = ((divisor > 0) == (dividend > 0));
  if (wasRoundedDown) 
    return roundedTowardsZeroQuotient + 1;
  else
    return roundedTowardsZeroQuotient;
}

Ist das klug? Nicht hübsch? Kurz? Nein. Entsprechend der Spezifikation? Ich glaube schon, aber ich habe es nicht vollständig getestet. Es sieht aber ziemlich gut aus.

Wir sind Profis hier; Verwenden Sie gute technische Praktiken. Erforschen Sie Ihre Tools, geben Sie das gewünschte Verhalten an, betrachten Sie zuerst Fehlerfälle und schreiben Sie den Code, um seine offensichtliche Richtigkeit hervorzuheben. Und wenn Sie einen Fehler finden, prüfen Sie zunächst, ob Ihr Algorithmus stark fehlerhaft ist, bevor Sie zufällig die Vergleichsrichtungen vertauschen und bereits funktionierende Dinge auflösen.

Alle Antworten hier scheinen bisher eher zu kompliziert.

In C # und Java müssen Sie für eine positive Dividende und einen Divisor einfach Folgendes tun:

( dividend + divisor - 1 ) / divisor 

Quelle: Number Conversion, Roland Backhouse, 2001

Die endgültige int-basierte Antwort

Für vorzeichenbehaftete Ganzzahlen:

int div = a / b;
if (((a ^ b) >= 0) && (a % b != 0))
    div++;

Für vorzeichenlose Ganzzahlen:

int div = a / b;
if (a % b != 0)
    div++;

Die Begründung für diese Antwort

Die Ganzzahldivision ' /' wird definiert, um gegen Null zu runden (7.7.2 der Spezifikation), aber wir wollen aufrunden. Dies bedeutet, dass negative Antworten bereits korrekt gerundet sind, positive Antworten jedoch angepasst werden müssen.

Positive Antworten ungleich Null sind leicht zu erkennen, aber die Antwort Null ist etwas schwieriger, da dies entweder das Aufrunden eines negativen Werts oder das Abrunden eines positiven Werts sein kann.

Am sichersten ist es, zu erkennen, wann die Antwort positiv sein sollte, indem überprüft wird, ob die Vorzeichen beider Ganzzahlen identisch sind. Der ganzzahlige xor-Operator ' ^' für die beiden Werte führt in diesem Fall zu einem 0-Vorzeichenbit, was ein nicht negatives Ergebnis bedeutet. Bei der Prüfung wird daher (a ^ b) >= 0festgestellt, dass das Ergebnis vor dem Runden positiv sein sollte. Beachten Sie auch, dass für vorzeichenlose Ganzzahlen jede Antwort offensichtlich positiv ist, sodass diese Prüfung weggelassen werden kann.

Die einzige verbleibende Prüfung ist dann, ob eine Rundung aufgetreten ist, für die a % b != 0die Arbeit erledigt wird.

Gewonnene Erkenntnisse

Arithmetik (ganzzahlig oder anders) ist bei weitem nicht so einfach, wie es scheint. Immer sorgfältig überlegen.

Auch wenn meine endgültige Antwort vielleicht nicht so "einfach" oder "offensichtlich" oder vielleicht sogar "schnell" ist wie die Gleitkomma-Antworten, hat sie für mich eine sehr starke Erlösungsqualität. Ich habe jetzt die Antwort durchdacht , also bin ich mir tatsächlich sicher, dass sie richtig ist (bis mir jemand schlauer etwas anderes sagt - verstohlener Blick in Erics Richtung -).

Um das gleiche Gefühl der Gewissheit über die Gleitkommaantwort zu erhalten, müsste ich mehr (und möglicherweise komplizierter) darüber nachdenken, ob es Bedingungen gibt, unter denen die Gleitkommapräzision im Weg stehen könnte, und ob dies Math.Ceilingmöglicherweise der Fall ist etwas Unerwünschtes an "genau den richtigen" Eingängen.

Der Weg reiste

Ersetzen (Anmerkung: Ich habe die zweite myInt1durch ersetzt myInt2, vorausgesetzt, Sie haben das gemeint):

(int)Math.Ceiling((double)myInt1 / myInt2)

mit:

(myInt1 - 1 + myInt2) / myInt2

Die einzige Einschränkung besteht darin, dass myInt1 - 1 + myInt2Sie möglicherweise nicht das bekommen, was Sie erwarten , wenn der von Ihnen verwendete Integer-Typ überläuft.

Grund dafür ist falsch : -1000000 und 3999 sollten -250 ergeben, dies ergibt -249

BEARBEITEN:
Da dies den gleichen Fehler wie die andere ganzzahlige Lösung für negative myInt1Werte aufweist, ist es möglicherweise einfacher, Folgendes zu tun:

int rem;
int div = Math.DivRem(myInt1, myInt2, out rem);
if (rem > 0)
  div++;

Dies sollte das richtige Ergebnis liefern, wenn divnur ganzzahlige Operationen verwendet werden.

Grund dafür ist falsch : -1 und -5 sollten 1 ergeben, dies ergibt 0

BEARBEITEN (noch einmal mit Gefühl):
Der Divisionsoperator rundet gegen Null; Für negative Ergebnisse ist dies genau richtig, sodass nur nicht negative Ergebnisse angepasst werden müssen. Wenn wir auch bedenken, dass DivRemnur a /und a ausgeführt %werden, überspringen wir den Anruf (und beginnen mit dem einfachen Vergleich, um eine Modulo-Berechnung zu vermeiden, wenn sie nicht benötigt wird):

int div = myInt1 / myInt2;
if ((div >= 0) && (myInt1 % myInt2 != 0))
    div++;

Grund dafür ist falsch : -1 und 5 sollten 0 ergeben, dies ergibt 1

(Zu meiner eigenen Verteidigung des letzten Versuchs hätte ich niemals eine begründete Antwort versuchen sollen, während mein Verstand mir sagte, ich sei 2 Stunden zu spät zum Schlafen)

Perfekte Chance, eine Erweiterungsmethode zu verwenden:

public static class Int32Methods
{
    public static int DivideByAndRoundUp(this int number, int divideBy)
    {                        
        return (int)Math.Ceiling((float)number / (float)divideBy);
    }
}

Dies macht Ihren Code auch überlesbar:

int result = myInt.DivideByAndRoundUp(4);

Sie könnten einen Helfer schreiben.

static int DivideRoundUp(int p1, int p2) {
  return (int)Math.Ceiling((double)p1 / p2);
}

Sie könnten so etwas wie das Folgende verwenden.

a / b + ((Math.Sign(a) * Math.Sign(b) > 0) && (a % b != 0)) ? 1 : 0)

Einige der oben genannten Antworten verwenden Floats. Dies ist ineffizient und wirklich nicht erforderlich. Für Ints ohne Vorzeichen ist dies eine effiziente Antwort für int1 / int2:

(int1 == 0) ? 0 : (int1 - 1) / int2 + 1;

Für signierte Ints ist dies nicht korrekt

Das Problem bei allen Lösungen hier ist entweder, dass sie eine Besetzung benötigen oder dass sie ein numerisches Problem haben. Casting auf Float oder Double ist immer eine Option, aber wir können es besser machen.

Wenn Sie den Code der Antwort von @jerryjvl verwenden

int div = myInt1 / myInt2;
if ((div >= 0) && (myInt1 % myInt2 != 0))
    div++;

Es liegt ein Rundungsfehler vor. 1/5 würde aufrunden, weil 1% 5! = 0. Dies ist jedoch falsch, da nur gerundet wird, wenn Sie die 1 durch eine 3 ersetzen, sodass das Ergebnis 0,6 ist. Wir müssen einen Weg finden, um aufzurunden, wenn die Berechnung einen Wert größer oder gleich 0,5 ergibt. Das Ergebnis des Modulo-Operators im oberen Beispiel hat einen Bereich von 0 bis myInt2-1. Die Rundung erfolgt nur, wenn der Rest mehr als 50% des Divisors beträgt. Der angepasste Code sieht also folgendermaßen aus:

int div = myInt1 / myInt2;
if (myInt1 % myInt2 >= myInt2 / 2)
    div++;

Natürlich haben wir auch bei myInt2 / 2 ein Rundungsproblem, aber dieses Ergebnis bietet Ihnen eine bessere Rundungslösung als die anderen auf dieser Site.