Wie kann man das Ergebnis der Ganzzahldivision aufrunden?

335

Ich denke insbesondere darüber nach, wie Paginierungssteuerelemente angezeigt werden, wenn eine Sprache wie C # oder Java verwendet wird.

Wenn ich x Elemente habe, die in Blöcken von y pro Seite angezeigt werden sollen, wie viele Seiten werden benötigt?

Ian Nelson
quelle
1
Vermisse ich etwas y / x + 1 funktioniert hervorragend (vorausgesetzt, Sie wissen, dass der Operator / immer abrundet).
Rikkit
51
@rikkit - Wenn y und x gleich sind, ist y / x + 1 eins zu hoch.
Ian Nelson
1
Für alle, die dies gerade finden, vermeidet diese Antwort auf eine betrogene Frage eine unnötige Konvertierung in Double und vermeidet Überlaufprobleme sowie eine klare Erklärung.
ZX9
2
@ IanNelson allgemeiner, wenn xdurch teilbar ist y, y/x + 1wäre eine zu hoch.
Ohad Schneider
1
@ ZX9 Nein, Überlaufbedenken werden nicht vermieden. Es ist genau die gleiche Lösung wie Ian Nelson hier.
user247702

Antworten:

478

Eine elegante Lösung gefunden:

int pageCount = (records + recordsPerPage - 1) / recordsPerPage;

Quelle: Number Conversion, Roland Backhouse, 2001

Ian Nelson
quelle
12
-1 wegen des Überlauffehlers, auf den Brandon DuRette hingewiesen hat
finnw
30
Herr Obvious sagt: Denken Sie daran, sicherzustellen, dass recordsPerPage nicht Null ist
Adam Gent
7
Gute Arbeit, ich kann nicht glauben, dass C # keine ganzzahlige Obergrenze hat.
Gosukiwi
2
Ja, hier stolpere ich Mitte 2017 über diese großartige Antwort, nachdem ich einige viel komplexere Ansätze ausprobiert habe.
Mifo
1
Für Sprachen mit einem geeigneten Euklidian-Divisionsoperator wie Python wäre ein noch einfacherer Ansatz pageCount = -((-records) // recordsPerPage).
Supercat
194

Die Konvertierung in Gleitkomma und zurück scheint auf CPU-Ebene eine enorme Zeitverschwendung zu sein.

Ian Nelsons Lösung:

int pageCount = (records + recordsPerPage - 1) / recordsPerPage;

Kann vereinfacht werden zu:

int pageCount = (records - 1) / recordsPerPage + 1;

AFAICS, dies hat nicht den Überlauffehler, auf den Brandon DuRette hingewiesen hat, und da er nur einmal verwendet wird, müssen Sie die recordsPerPage nicht speziell speichern, wenn sie von einer teuren Funktion stammt, um den Wert aus einer Konfigurationsdatei oder abzurufen etwas.

Das heißt, dies könnte ineffizient sein, wenn config.fetch_value eine Datenbanksuche verwendet hat oder so:

int pageCount = (records + config.fetch_value('records per page') - 1) / config.fetch_value('records per page');

Dadurch wird eine Variable erstellt, die Sie nicht wirklich benötigen. Dies hat wahrscheinlich (geringfügige) Auswirkungen auf den Speicher und ist einfach zu viel Eingabe:

int recordsPerPage = config.fetch_value('records per page')
int pageCount = (records + recordsPerPage - 1) / recordsPerPage;

Dies ist alles eine Zeile und ruft die Daten nur einmal ab:

int pageCount = (records - 1) / config.fetch_value('records per page') + 1;
rjmunro
quelle
5
+1, das Problem, dass null Datensätze immer noch 1 pageCount zurückgeben, ist praktisch, da ich immer noch 1 Seite möchte, auf der der Platzhalter / die gefälschte Zeile "Keine Datensätze entsprechen Ihren Kriterien" angezeigt wird, um Probleme mit "0 Seitenzahlen" zu vermeiden Paginierungskontrolle, die Sie verwenden.
Timothy Walters
27
Beachten Sie, dass die beiden Lösungen nicht dieselbe pageCount für Null-Datensätze zurückgeben. Diese vereinfachte Version gibt 1 pageCount für null Datensätze zurück, während die Roland Backhouse-Version 0 pageCount zurückgibt. Gut, wenn Sie dies wünschen, aber die beiden Gleichungen sind nicht äquivalent, wenn sie von der Ganzzahldivision im C # / Java-Stil ausgeführt werden.
Ian Nelson
10
winzige Vereinfachung für Klarheit für Leute, die es scannen und fehlende Bodmas beim Wechsel zur Vereinfachung von der Nelson-Lösung (wie ich es das erste Mal getan habe!), die Vereinfachung mit Klammern ist ... int pageCount = ((records - 1) / recordsPerPage) + 1;
Dave Heywood
1
Sie sollten der vereinfachten Version Klammern hinzufügen, damit sie nicht von einer bestimmten Reihenfolge der Operationen abhängt. dh ((records - 1) / recordsPerPage) + 1.
Martin
1
@ Ian, diese Antwort gibt nicht IMMER 1 zurück. Sie kann 0 zurückgeben, wenn Ihre recordsPerPage "1" ist und 0 Datensätze vorhanden sind : -1 / 1 + 1 = 0. Dies ist zwar kein sehr häufiges Ereignis, es ist jedoch wichtig zu berücksichtigen, ob Benutzer die Seitengröße anpassen können. Erlauben Sie Benutzern entweder nicht, eine Seitengröße von 1 zu haben, überprüfen Sie die Seitengröße oder beides (wahrscheinlich vorzuziehen, um unerwartetes Verhalten zu vermeiden).
Michael
81

Für C # besteht die Lösung darin, die Werte in ein Double umzuwandeln (da Math.Ceiling ein Double verwendet):

int nPages = (int)Math.Ceiling((double)nItems / (double)nItemsPerPage);

In Java sollten Sie dasselbe mit Math.ceil () tun.

Huppie
quelle
4
Warum ist diese Antwort so weit unten, wenn die Operation explizit nach C # fragt?
Felickz
2
Sie müssen die Ausgabe auch in umwandeln, intda je nach Eingabetyp Math.Ceilingein doubleoder zurückgegeben decimalwird.
DanM7
14
weil es extrem ineffizient ist
Zar Shardan
6
Es mag ineffizient sein, aber es ist extrem leicht zu verstehen. Bei der Berechnung einer Seitenzahl wird normalerweise einmal pro Anforderung ein Leistungsverlust nicht messbar sein.
Jared Kells
1
Es ist kaum besser lesbar als dieses "(Dividende + (Divisor - 1)) / Divisor;" Es ist auch langsam und erfordert die Mathematikbibliothek.
Brötchen
68

Dies sollte Ihnen geben, was Sie wollen. Sie werden auf jeden Fall x Elemente geteilt durch y Elemente pro Seite wollen. Das Problem ist, wenn ungerade Zahlen auftauchen. Wenn es also eine Teilseite gibt, möchten wir auch eine Seite hinzufügen.

int x = number_of_items;
int y = items_per_page;

// with out library
int pages = x/y + (x % y > 0 ? 1 : 0)

// with library
int pages = (int)Math.Ceiling((double)x / (double)y);
Nick Berardi
quelle
5
x / y + !! (x% y) vermeidet den Zweig für C-ähnliche Sprachen. Die Chancen stehen gut, aber Ihr Compiler macht das trotzdem.
Rhys Ulerich
2
+1 für nicht überlaufen wie die obigen Antworten ... obwohl das Konvertieren von Ints in Doubles nur für Math.ceiling und dann wieder zurück eine schlechte Idee in leistungsempfindlichem Code ist.
Zahnrad
3
@RhysUlerich, das in c # nicht funktioniert (kann ein int nicht direkt in ein bool konvertieren). Die Lösung von rjmunro ist meiner Meinung nach der einzige Weg, eine Verzweigung zu vermeiden.
Smead
18

Die von Ian bereitgestellte ganzzahlige mathematische Lösung ist nett, leidet jedoch an einem ganzzahligen Überlauffehler. Unter der Annahme, dass alle Variablen vorhanden sind int, könnte die Lösung neu geschrieben werden, um longMathematik zu verwenden und den Fehler zu vermeiden:

int pageCount = (-1L + records + recordsPerPage) / recordsPerPage;

Wenn a recordsist long, bleibt der Fehler bestehen. Die Modullösung hat den Fehler nicht.

Brandon DuRette
quelle
4
Ich glaube nicht, dass Sie diesen Fehler in dem vorgestellten Szenario realistisch treffen werden. 2 ^ 31 Datensätze sind ziemlich viel, um durchblättern zu müssen.
rjmunro
8
@rjmunro, reales Beispiel hier
finnw
@finnw: AFAICS, auf dieser Seite gibt es kein reales Beispiel, nur einen Bericht von jemand anderem, der den Fehler in einem theoretischen Szenario gefunden hat.
rjmunro
5
Ja, ich war pedantisch, als ich auf den Fehler hinwies. Viele Fehler können auf Dauer bestehen, ohne jemals Probleme zu verursachen. In der JDK-Implementierung von binarySearch gab es neun Jahre lang einen Fehler derselben Form, bevor ihn jemand meldete ( googleresearch.blogspot.com/2006/06/… ). Ich denke, die Frage ist, unabhängig davon, wie unwahrscheinlich es ist, dass Sie auf diesen Fehler stoßen, warum Sie ihn nicht im Voraus beheben.
Brandon DuRette
4
Es sollte auch beachtet werden, dass es nicht nur auf die Anzahl der ausgelagerten Elemente ankommt, sondern auch auf die Seitengröße. Wenn Sie also eine Bibliothek erstellen und jemand beschließt, keine Seite zu erstellen, indem er 2 ^ 31-1 (Integer.MAX_VALUE) als Seitengröße übergibt, wird der Fehler ausgelöst.
Brandon DuRette
7

Eine Variante von Nick Berardis Antwort , die einen Zweig vermeidet:

int q = records / recordsPerPage, r = records % recordsPerPage;
int pageCount = q - (-r >> (Integer.SIZE - 1));

Hinweis: (-r >> (Integer.SIZE - 1))besteht aus dem Vorzeichenbit von r, das 32 Mal wiederholt wird (dank der Vorzeichenerweiterung des >>Operators). Dies rergibt 0, wenn es Null oder negativ ist, -1, wenn res positiv ist. Das Subtrahieren von qbewirkt also, dass 1 if addiert wird records % recordsPerPage > 0.

finnw
quelle
4

Für Datensätze == 0 ergibt die Lösung von rjmunro 1. Die richtige Lösung ist 0. Wenn Sie jedoch wissen, dass Datensätze> 0 sind (und ich bin sicher, dass wir alle recordsPerPage> 0 angenommen haben), liefert die Lösung von rjmunro korrekte Ergebnisse und hat keine der Überlaufprobleme.

int pageCount = 0;
if (records > 0)
{
    pageCount = (((records - 1) / recordsPerPage) + 1);
}
// no else required

Alle ganzzahligen mathematischen Lösungen sind effizienter als alle Gleitkomma-Lösungen.

Mike
quelle
Es ist unwahrscheinlich, dass diese Methode einen Leistungsengpass darstellt. Und wenn ja, sollten Sie auch die Kosten der Niederlassung berücksichtigen.
Finnw
4

Benötigen Sie eine Erweiterungsmethode:

    public static int DivideUp(this int dividend, int divisor)
    {
        return (dividend + (divisor - 1)) / divisor;
    }

Keine Kontrollen hier (Überlauf, DivideByZero usw.). Wenn Sie möchten, können Sie diese hinzufügen. Übrigens, für diejenigen, die sich Sorgen über den Aufwand für Methodenaufrufe machen, könnten einfache Funktionen wie diese sowieso vom Compiler eingebunden werden, daher denke ich nicht, dass dies von Belang ist. Prost.

PS Vielleicht ist es auch nützlich, sich dessen bewusst zu sein (der Rest wird erhalten):

    int remainder; 
    int result = Math.DivRem(dividend, divisor, out remainder);
Nicholas Petersen
quelle
1
Das ist falsch. Beispiel: DivideUp(4, -2)Gibt 0 zurück (sollte -2 sein). Dies gilt nur für nicht negative Ganzzahlen, die aus der Antwort oder der Funktionsschnittstelle nicht ersichtlich sind.
Thash
6
Thash, warum machst du nicht etwas Nützliches, wie den kleinen zusätzlichen Scheck hinzuzufügen, wenn die Zahl negativ ist, anstatt meine Antwort abzustimmen und fälschlicherweise die pauschale Aussage zu machen: "Das ist falsch", obwohl es tatsächlich nur eine Kante ist Fall. Ich habe bereits klargestellt, dass Sie zuerst andere Überprüfungen durchführen sollten: "Keine Überprüfungen hier (Überlauf, DivideByZero usw.). Fügen Sie diese hinzu, wenn Sie möchten ."
Nicholas Petersen
1
In der Frage "Ich denke insbesondere darüber nach, wie Paginierungssteuerelemente angezeigt werden sollen " wurde erwähnt, sodass negative Zahlen sowieso außerhalb der Grenzen lagen. Wieder tun Sie einfach etwas Nützliches und schlagen Sie eine zusätzliche Prüfung vor, wenn Sie möchten, es ist ein Mann mit Teamleistung.
Nicholas Petersen
Ich wollte nicht unhöflich sein und es tut mir leid, wenn Sie es so sehen. Die Frage war "Wie man das Ergebnis der Ganzzahldivision aufrundet". Der Autor erwähnte die Paginierung, aber andere Menschen haben möglicherweise andere Bedürfnisse. Ich denke, es wäre besser, wenn Ihre Funktion irgendwie widerspiegeln würde, dass sie für negative Ganzzahlen nicht funktioniert, da sie nicht aus der Schnittstelle hervorgeht (zum Beispiel ein anderer Name oder andere Argumenttypen). Um mit negativen ganzen Zahlen zu arbeiten, können Sie beispielsweise einen absoluten Wert der Dividende und des Divisors nehmen und das Ergebnis mit seinem Vorzeichen multiplizieren.
Thash
2

Eine andere Alternative ist die Verwendung der Funktion mod () (oder '%'). Wenn der Rest ungleich Null ist, erhöhen Sie das ganzzahlige Ergebnis der Division.

Jarod Elliott
quelle
1

Ich mache folgendes, behandle eventuelle Überläufe:

var totalPages = totalResults.IsDivisble(recordsperpage) ? totalResults/(recordsperpage) : totalResults/(recordsperpage) + 1;

Verwenden Sie diese Erweiterung, wenn 0 Ergebnisse vorliegen:

public static bool IsDivisble(this int x, int n)
{
           return (x%n) == 0;
}

Auch für die aktuelle Seitenzahl (wurde nicht gefragt, könnte aber nützlich sein):

var currentPage = (int) Math.Ceiling(recordsperpage/(double) recordsperpage) + 1;
Sam Jones
quelle
0

Alternative zum Entfernen der Verzweigung beim Testen auf Null:

int pageCount = (records + recordsPerPage - 1) / recordsPerPage * (records != 0);

Nicht sicher, ob dies in C # funktioniert, sollte in C / C ++ funktionieren.

Fluss
quelle
-1

Eine generische Methode, über deren Ergebnis Sie iterieren können, kann von Interesse sein:

public static Object[][] chunk(Object[] src, int chunkSize) {

    int overflow = src.length%chunkSize;
    int numChunks = (src.length/chunkSize) + (overflow>0?1:0);
    Object[][] dest = new Object[numChunks][];      
    for (int i=0; i<numChunks; i++) {
        dest[i] = new Object[ (i<numChunks-1 || overflow==0) ? chunkSize : overflow ];
        System.arraycopy(src, i*chunkSize, dest[i], 0, dest[i].length); 
    }
    return dest;
}
Jeremy Hadfied
quelle
Guave hat eine ähnliche Methode ( Lists.partition(List, int)) und ironischerweise leidet die size()Methode der resultierenden List(ab r09) unter dem in Brandon DuRettes Antwort erwähnten Überlauffehler .
Finnw
-2

Ich hatte ein ähnliches Bedürfnis, bei dem ich Minuten in Stunden und Minuten umrechnen musste. Was ich benutzt habe war:

int hrs = 0; int mins = 0;

float tm = totalmins;

if ( tm > 60 ) ( hrs = (int) (tm / 60);

mins = (int) (tm - (hrs * 60));

System.out.println("Total time in Hours & Minutes = " + hrs + ":" + mins);
Richard Parsons
quelle
-2

Folgendes sollte besser runden als die oben genannten Lösungen, jedoch auf Kosten der Leistung (aufgrund der Gleitkommaberechnung von 0,5 * rctDenominator):

uint64_t integerDivide( const uint64_t& rctNumerator, const uint64_t& rctDenominator )
{
  // Ensure .5 upwards is rounded up (otherwise integer division just truncates - ie gives no remainder)
  return (rctDenominator == 0) ? 0 : (rctNumerator + (int)(0.5*rctDenominator)) / rctDenominator;
}
Jim Watson
quelle
-4

Sie möchten eine Gleitkommadivision durchführen und dann die Deckenfunktion verwenden, um den Wert auf die nächste Ganzzahl aufzurunden.

Kibbee
quelle