Ganzzahldivision runden (anstatt abzuschneiden)

Ich wollte wissen, wie ich eine Zahl auf die nächste ganze Zahl runden kann. Wenn ich zum Beispiel hätte:

int a = 59 / 4;

was 14,75 wäre, wenn es in Fließkomma berechnet würde; Wie kann ich das Ergebnis als 15 in “a” speichern?

Das Standard-Idiom für das Aufrunden ganzer Zahlen lautet:

int a = (59 + (4 - 1)) / 4;

Du addierst den Divisor minus eins zum Dividenden.

Ein Code, der für jedes Vorzeichen in Dividenden und Divisoren funktioniert:

int divRoundClosest(const int n, const int d)
{
  return ((n < 0) ^ (d < 0)) ? ((n - d/2)/d) : ((n + d/2)/d);
}

Als Antwort auf einen Kommentar „Warum funktioniert das eigentlich?“ können wir das auseinanderbrechen. Beobachten Sie das zunächst n/d wäre der Quotient, aber er wird gegen Null gekürzt, nicht gerundet. Sie erhalten ein gerundetes Ergebnis, wenn Sie vor dem Dividieren den halben Nenner zum Zähler addieren, aber nur, wenn Zähler und Nenner das gleiche Vorzeichen haben. Wenn sich die Vorzeichen unterscheiden, müssen Sie vor dem Dividieren die Hälfte des Nenners subtrahieren. Das alles zusammen:

(n < 0) is false (zero) if n is non-negative
(d < 0) is false (zero) if d is non-negative
((n < 0) ^ (d < 0)) is true if n and d have opposite signs
(n + d/2)/d is the rounded quotient when n and d have the same sign
(n - d/2)/d is the rounded quotient when n and d have opposite signs

Wenn Sie ein Makro bevorzugen:

#define DIV_ROUND_CLOSEST(n, d) ((((n) < 0) ^ ((d) < 0)) ? (((n) - (d)/2)/(d)) : (((n) + (d)/2)/(d)))

Das Linux-Kernel-Makro DIV_ROUND_CLOSEST funktioniert nicht für negative Teiler!

int a = 59.0f / 4.0f + 0.5f;

Dies funktioniert nur beim Zuweisen zu einem int, da es alles nach dem „.“ verwirft.

Bearbeiten:
Diese Lösung funktioniert nur in den einfachsten Fällen. Eine robustere Lösung wäre:

unsigned int round_closest(unsigned int dividend, unsigned int divisor)
{
    return (dividend + (divisor / 2)) / divisor;
}

Sie sollten stattdessen so etwas verwenden:

int a = (59 - 1)/ 4 + 1;

Ich gehe davon aus, dass Sie wirklich versuchen, etwas Allgemeineres zu tun:

int divide(x, y)
{
   int a = (x -1)/y +1;

   return a;
}

x + (y-1) kann überlaufen und ein falsches Ergebnis liefern; wohingegen x – 1 nur dann unterläuft, wenn x = min_int …

(Bearbeitet) Das Runden von ganzen Zahlen mit Gleitkomma ist die einfachste Lösung für dieses Problem; je nach Problemstellung ist dies jedoch möglich. Beispielsweise kann in eingebetteten Systemen die Gleitkommalösung zu kostspielig sein.

Dies mit ganzzahliger Mathematik zu tun, erweist sich als ziemlich schwierig und ein wenig unintuitiv. Die erste gepostete Lösung funktionierte gut für das Problem, für das ich sie verwendet hatte, aber nachdem ich die Ergebnisse über den Bereich der ganzen Zahlen charakterisiert hatte, stellte sich heraus, dass sie im Allgemeinen sehr schlecht war. Wenn Sie mehrere Bücher über Bit-Twiddling und eingebettete Mathematik durchsehen, erhalten Sie nur wenige Ergebnisse. Ein paar Anmerkungen. Zuerst habe ich nur auf positive ganze Zahlen getestet, meine Arbeit beinhaltet keine negativen Zähler oder Nenner. Zweitens ist ein umfassender Test von 32-Bit-Ganzzahlen rechenintensiv, also habe ich mit 8-Bit-Ganzzahlen begonnen und dann sichergestellt, dass ich mit 16-Bit-Ganzzahlen ähnliche Ergebnisse erhalte.

Ich begann mit den 2 Lösungen, die ich zuvor vorgeschlagen hatte:

#define DIVIDE_WITH_ROUND(N, D) (((N) == 0) ? 0:(((N * 10)/D) + 5)/10)

#define DIVIDE_WITH_ROUND(N, D) (N == 0) ? 0:(N - D/2)/D + 1;

Mein Gedanke war, dass die erste Version mit großen Zahlen überlaufen würde und die zweite mit kleinen Zahlen unterlaufen würde. 2 Dinge habe ich nicht berücksichtigt. 1.) Das 2. Problem ist eigentlich rekursiv, da Sie D/2 richtig runden müssen, um die richtige Antwort zu erhalten. 2.) Im ersten Fall läuft man oft über und dann wieder unter, wobei sich beides gegenseitig aufhebt. Hier ist ein Fehlerdiagramm der beiden (falschen) Algorithmen:

Dieses Diagramm zeigt, dass der erste Algorithmus nur für kleine Nenner (0 < d < 10) falsch ist. Unerwarteterweise handhabt es sich tatsächlich groß Zähler besser als die 2. Version.

Hier ist ein Plot des 2. Algorithmus:

Wie erwartet schlägt es bei kleinen Zählern fehl, aber auch bei größeren Zählern als die 1. Version.

Dies ist eindeutig der bessere Ausgangspunkt für eine korrekte Version:

#define DIVIDE_WITH_ROUND(N, D) (((N) == 0) ? 0:(((N * 10)/D) + 5)/10)

Wenn Ihr Nenner > 10 ist, funktioniert dies korrekt.

Für D == 1 ist ein Sonderfall erforderlich, geben Sie einfach N zurück. Für D == 2 ist ein Sonderfall erforderlich, = N/2 + (N & 1) // Aufrunden, wenn ungerade.

D >= 3 hat auch Probleme, sobald N groß genug wird. Es stellt sich heraus, dass größere Nenner nur Probleme mit größeren Zählern haben. Für vorzeichenbehaftete 8-Bit-Zahlen sind die Problempunkte

if (D == 3) && (N > 75))
else if ((D == 4) && (N > 100))
else if ((D == 5) && (N > 125))
else if ((D == 6) && (N > 150))
else if ((D == 7) && (N > 175))
else if ((D == 8) && (N > 200))
else if ((D == 9) && (N > 225))
else if ((D == 10) && (N > 250))

(D/N für diese zurückgeben)

Im Allgemeinen liegt der Punkt, an dem ein bestimmter Zähler schlecht wird, irgendwo in der Nähe
N > (MAX_INT - 5) * D/10

Das ist nicht exakt, aber nah dran. Beim Arbeiten mit 16-Bit- oder größeren Zahlen ist der Fehler < 1%, wenn Sie für diese Fälle nur eine C-Division (Abschneiden) durchführen.

Für vorzeichenbehaftete 16-Bit-Zahlen wären die Tests

if ((D == 3) && (N >= 9829))
else if ((D == 4) && (N >= 13106))
else if ((D == 5) && (N >= 16382))
else if ((D == 6) && (N >= 19658))
else if ((D == 7) && (N >= 22935))
else if ((D == 8) && (N >= 26211))
else if ((D == 9) && (N >= 29487))
else if ((D == 10) && (N >= 32763))

Natürlich würde für vorzeichenlose Ganzzahlen MAX_INT durch MAX_UINT ersetzt werden. Ich bin sicher, es gibt eine genaue Formel zur Bestimmung des größten N, das für ein bestimmtes D und eine bestimmte Anzahl von Bits funktioniert, aber ich habe keine Zeit mehr, an diesem Problem zu arbeiten …

(Mir scheint diese Grafik im Moment zu fehlen, ich werde sie später bearbeiten und hinzufügen.) Dies ist eine Grafik der 8-Bit-Version mit den oben erwähnten Sonderfällen:![8 bit signed with special cases for 0 < N <= 10 3

Note that for 8 bit the error is 10% or less for all errors in the graph, 16 bit is < 0.1%.

As written, you’re performing integer arithmetic, which automatically just truncates any decimal results. To perform floating point arithmetic, either change the constants to be floating point values:

int a = round(59.0 / 4);

Or cast them to a float or other floating point type:

int a = round((float)59 / 4);

Either way, you need to do the final rounding with the round() function in the math.h header, so be sure to #include <math.h> and use a C99 compatible compiler.

From Linux kernel (GPLv2):

/*
 * Divide positive or negative dividend by positive divisor and round
 * to closest integer. Result is undefined for negative divisors and
 * for negative dividends if the divisor variable type is unsigned.
 */
#define DIV_ROUND_CLOSEST(x, divisor)(          \
{                           \
    typeof(x) __x = x;              \
    typeof(divisor) __d = divisor;          \
    (((typeof(x))-1) > 0 ||             \
     ((typeof(divisor))-1) > 0 || (__x) > 0) ?  \
        (((__x) + ((__d) / 2)) / (__d)) :   \
        (((__x) - ((__d) / 2)) / (__d));    \
}                           \
)