Rundung integer-division (statt abschneiden)
Ich war neugierig zu erfahren, wie ich kann, Runden Sie eine Zahl auf die nächste ganze Zahl. Wenn ich beispielsweise hatte:
int a = 59 / 4;
wäre 14.75 wenn Sie für die Berechnung im floating-point; wie kann ich speichern das Ergebnis als 15 in "a"?
Bitte klären: Die nächste Zehntel (14.8) oder die nächste ganze Zahl (15) ?
denn a ist ein int, es werden gerundet auf die nächste ganze Zahl, nicht wahr?
sorry nächste ganze Zahl
Sieht so aus, aber warum dann sagen, "die nächste Zehntel" in der Aufgabenstellung? Entweder die Aussage ist falsch, oder es gibt etwas, was der OP machen will, dass er nicht deutlich angeben. Das ist die Idee hinter der Frage für eine Klarstellung.
hmm, ja, guter Punkt! Ich bin mir nicht sicher, warum er das gefragt Zehntel beim speichern das Ergebnis in eine Ganzzahl.
denn a ist ein int, es werden gerundet auf die nächste ganze Zahl, nicht wahr?
sorry nächste ganze Zahl
Sieht so aus, aber warum dann sagen, "die nächste Zehntel" in der Aufgabenstellung? Entweder die Aussage ist falsch, oder es gibt etwas, was der OP machen will, dass er nicht deutlich angeben. Das ist die Idee hinter der Frage für eine Klarstellung.
hmm, ja, guter Punkt! Ich bin mir nicht sicher, warum er das gefragt Zehntel beim speichern das Ergebnis in eine Ganzzahl.
InformationsquelleAutor Dave | 2010-03-11
Du musst angemeldet sein, um einen Kommentar abzugeben.
Dies funktioniert nur, wenn die Zuweisung an einen int als er verwirft alles, was nach dem '.'
Edit:
Diese Lösung funktioniert nur in den einfachsten Fällen. Eine robustere Lösung wäre:
Da bei Systemen ohne FPU, das macht wirklich, wirklich, schlechten code.
das ist das problem. die OP ' s Frage ist lösbar, ohne floating-point auf, und so wird nicht davon abhängig sein, FPU-Unterstützung vorhanden oder gut zu sein. auch, schneller (in dem Fall, dass viele diese berechnet werden müssen) auf den meisten Architekturen, einschließlich derer, die ansonsten fantastischen FPU-Unterstützung. beachten Sie auch, dass Ihre Lösung könnte problematisch sein, für größere zahlen, wo die floats nicht exakt darstellen, die ganzzahlige Werte gegeben.
-1, so erhält man die falsche Antwort, die für viele Werte, wenn sizeof(int) >= sizeof(float). Zum Beispiel, eine 32-bit-float verwendet einige bits stellen den Exponenten und so kann es nicht exakt darstellen, jeder 32-bit-int. So 12584491 / 3 = 4194830.333..., das sollte abrunden 4194830, aber auf meinem Rechner das nicht darstellen kann 12584491 genau in einen Schwimmer, der oben genannten Formel rundet auf die 4194831, die falsch ist. Mit doppelt sicherer.
Wirklich die Frage ist, warum Sie wollen, um Werte darzustellen, wie diese als integer-Typ. doppelt hält perfekt Ganzzahlen bis 2^53 und Sie können einfach angeben, wie Fehler, die gerundet wird.
InformationsquelleAutor 0xC0DEFACE
Den standard-idiom für Ganzzahl aufrunden ist:
Fügen Sie den divisor minus die Dividende.
Ugh...dann haben Sie zu denken...add (n - 1) / 2, mehr oder weniger. Für n == 4, Sie wollen x % n ∈ { 0, 1 } zu Runde nach unten, und x % n ∈ { 2, 3 } zu Runde bis. So, Sie brauchen, um hinzuzufügen, 2, n / 2. Für n == 5, Sie wollen x % n ∈ { 0, 1, 2 } zu Runde nach unten, und x % n ∈ { 3, 4 } in der Runde, so müssen Sie 2 wieder...also:
int i = (x + (n / 2)) / n;
?Diese Methode funktioniert für positive
int
. Aber wenn der divisor oder der dividend negativ ist, erzeugt es eine falsche Antwort. Der Hinweis auf @caf funktioniert entweder nicht.Die (original -) Titel und die Frage, die gestellt wird für zwei verschiedene Dinge. Der Titel sagt aufrunden (das ist, was Sie schon beantwortet), aber der Körper sagt Runde auf die nächste (das ist, was die akzeptierten Antworten versuche).
Nur Vorsicht, dass
c = (INT_MAX + (4 - 1)) / 4;
gibtc = -536870911
durch integer-überlauf...InformationsquelleAutor Jonathan Leffler
Einen code, der funktioniert für beliebige Zeichen in dividend und divisor:
Wenn Sie lieber ein makro:
Den linux-kernel makro DIV_ROUND_CLOSEST funktioniert nicht für negative Teiler!
int
Werte in der Nähe von min - /max-int, ist dies die beste Lösung bisher.Warum ist das tatsächlich funktioniert? Was ist das mathematische Konzept dahinter?
InformationsquelleAutor ericbn
Sollten Sie es stattdessen mit etwas wie:
Ich davon ausgehen, dass Sie wirklich versuchen, zu tun, etwas mehr allgemein:
x + (y-1) hat das Potenzial, zum überlauf zu geben, die zu falschen Ergebnissen führen; in der Erwägung, x - 1 wird nur der Unterlauf, wenn x = min_int...
warum würde 2.0333.. abgerundet 2 sein?
Dies funktioniert nicht, wenn x = 0. Das beabsichtigte Ergebnis von x/y Rundung auf, wenn x = 0 ist 0. Doch diese Lösung ergibt ein Ergebnis von 1. Die andere Lösung kommt, mit der richtigen Antwort.
Eigentlich ist diese Antwort nicht korrekt. Es funktioniert für ein paar zahlen, versäumt es aber auf ganz wenige. Siehe meine besser (hoffe ich) Antwort später in den thread.
(downvoted weil der Autor weist darauf hin, dies ist falsch)
InformationsquelleAutor WayneJ
(Bearbeitet)
Rundung von zahlen mit Fließkomma ist die einfachste Lösung für dieses problem; jedoch in Abhängigkeit von der problem-set ist möglich. Zum Beispiel in embedded systems die Gleitkomma-Lösung zu teuer.
Tun dies unter Verwendung der integer-Mathematik stellt sich heraus, zu schwer und ein wenig unintuitiv. Das erste gepostete Lösung war okay, für die das problem, das ich es verwendet hatte, aber nach der Charakterisierung der Ergebnisse in den Bereich von ganzen zahlen es stellte sich heraus, sehr schlecht im Allgemeinen. Auf der Suche durch mehrere Bücher, die auf bit-twiddling-und embedded-math return einige Ergebnisse.
Ein paar Notizen. Zuerst habe ich nur getestet für positive zahlen, meine Arbeit nicht mit negativen Zähler oder Nenner. Zweite und erschöpfenden test der 32-bit-Ganzzahlen ist, computational unerschwinglich und so begann ich mit 8-bit-Ganzzahlen und dann mades sicher, dass ich ähnliche Ergebnisse mit der 16-bit-Integer.
Begann ich mit dem 2 Lösungen, die ich vorher vorgeschlagen:
#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 würde überlauf mit großen zahlen und die zweite Unterlauf mit kleinen zahlen. Ich habe nicht 2 Sachen in Erwägung ziehen. 1.) das 2. problem ist eigentlich rekursiv, da bekommen Sie die richtige Antwort, Sie haben richtig Runde D/2. 2.) Im ersten Fall werden Sie oft überlaufen und dann Unterlauf, der zwei gegenseitig auslöschen.
Hier ist ein Fehler Handlung der beiden (falschen) algorithmen:
Diese Darstellung zeigt, dass der erste Algorithmus ist nur falsch für kleine Nenner (0 < d < 10). Unerwartet ist es tatsächlich behandelt großen Zähler besser als die 2. version.
Hier ist ein plot der 2. Algorithmus:
Als erwartet ausfällt für kleine Zähler aber auch nicht für größere Zähler als die 1. version.
Klar ist das die bessere Ausgangsbasis für eine korrekte version:
#define DIVIDE_WITH_ROUND(N, D) (((N) == 0) ? 0:(((N * 10)/D) + 5)/10)
Wenn Ihr Nenner ist, > 10 dann funktioniert das korrekt.
Einen speziellen Fall benötigt wird, für D == 1, return N.
Ein besonderer Fall ist erforderlich für D== 2, = N/2 + (N & 1) //aufrunden, wenn Sie ungerade.
D >= 3 hat auch Probleme, wenn N groß wird genug. Es stellt sich heraus, dass größere Nenner nur Probleme mit größeren Zähler. Für 8 bit signed Zahl der problem-Punkte sind
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))
(Rückgabe D/N für diese)
Also im Allgemeinen ist das die pointe, wo sich ein bestimmter Zähler schlecht bekommt, ist irgendwo rund
N > (MAX_INT - 5) * D/10
Dies ist nicht genau, aber in der Nähe. Bei der Arbeit mit 16-bit oder größeren zahlen wird die Fehlermeldung < 1%, wenn man nur eine C-teilen (Trunkierung) für diese Fälle.
Für 16-bit vorzeichenbehaftete zahlen würden die tests werden
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 für vorzeichenlose Ganzzahlen MAX_INT ersetzt werden würde mit MAX_UINT. Ich bin sicher, es gibt eine genaue Formel für die Bestimmung des größten N, die die Arbeit für ein bestimmtes D und die Anzahl der bits, aber ich habe nicht mehr Zeit für die Arbeit an diesem problem...
(Ich scheinen zu fehlen dieser graph ist im moment, werde ich Bearbeiten und später hinzufügen.)
Dies ist ein Diagramm der 8-bit-version mit dem speziellen oben aufgeführten Fälle:![8 bit signed mit speziellen Fällen für
0 < N <= 10
DreiBeachten Sie, dass bei 8 bit ist der Fehler 10% oder weniger für alle Fehler in der Grafik, 16 bit < 0.1%.
Sind Sie richtig. Das erste makro falsch war (ich fand dies heraus die harte Tour.) Dies erwies sich als schwieriger als ich erwartet hatte. Ich aktualisiert die post Anerkennung der Unrichtigkeit und einige weitere Diskussion.
InformationsquelleAutor WayneJ
Wie geschrieben, die Sie gerade ausführen integer-Arithmetik, die automatisch schneidet nur eine dezimale Ergebnisse. Zu führen Gleitkomma-Arithmetik, ändern Sie entweder die Konstanten Gleitkomma-Werte:
Oder werfen Sie einen
float
oder andere floating-point-Typ:Entweder Weg, müssen Sie die letzten Runden mit den
round()
Funktion in dermath.h
header, so sicher sein, zu#include <math.h>
und verwenden Sie einen C99-kompatibler compiler.float
(IEEE) Grenzen der nutzbare Bereich dieser Lösung zu abs(a/b) < 16,777,216.Oder vielleicht
lround
.InformationsquelleAutor Chris Lutz
Vom Linux-kernel (GPLv2):
typeof()
Teil C-oder eine compiler-spezifische Erweiterung?href="http://tigcc.ticalc.org/doc/gnuexts.html#SEC69" >Es ist eine GCC-Erweiterung. Sie ist nicht Teil von standard-C.
nette Möglichkeit um zu überprüfen, für signed vs. unsigned args in einem makro, also unsigned args verlassen können sich die Zweig-und extra-Anweisungen vollständig.
InformationsquelleAutor PauliusZ
Überprüfung, ob es ein Rest können Sie manuell roundup der quotient der ganzzahligen division.
dies ist immer aufrunden wie
ceil
Funktion, nicht eine richtige RundungInformationsquelleAutor user3707766
Andere nützliche MAKROS (MÜSSEN):
Sicher, es sieht aus wie ein schlimmer Fall von LISP, aber das weglassen der Klammern um jedes argument und dann auswerten ABS(4 & -1) ist noch schlimmer.
Er will
ROUND
, nichtCEIL
InformationsquelleAutor Magnetron
Hier ist meine Lösung. Ich mag es, weil ich finde es besser lesbar-und weil es keine Verzweigung (weder ifs noch ternaries).
Vollständige test-Programm, das zeigt, beabsichtigte Verhalten:
&
im((a ^ b) & 0x80000000) >> 31;
ist redundant, da die niedrigen bits werden weggeworfen, nach der Schicht ehInformationsquelleAutor Rasmus Rønn Nielsen
Kreditaufnahme von @ericbn ich prefere definiert, wie
InformationsquelleAutor zevero
zB 59/4 Quotient = 14, tempY = 2, Rest = 3, Rest >= tempY also quotient = 15;
Dies funktioniert nicht richtig, für negative zahlen - betrachten
divide(-59, 4)
.InformationsquelleAutor Abhay Lolekar
Sieht es jetzt besser?
dies ist die schlechteste Lösung. Denn 2 langsame Divisionen sind nicht die Menschen wollen zu tun. Und b können erhalten werden durch abschneiden eines zu tun, anstatt eine weitere division
InformationsquelleAutor Siva Dhatra
versuchen mit math ceil-Funktion, das macht aufgerundet. Math Ceil !
InformationsquelleAutor Samuel Santos
Wenn Sie positive ganze zahlen dividieren können Sie bei gedrückter Umschalttaste, tun die Teilung und überprüfen Sie dann die etwas rechts von der realen b0. In anderen Worten, 100/8 ist 12,5 aber zurückkehren würde, 12. Wenn Sie tun, (100<<1)/8 können Sie überprüfen, b0 und dann in der Runde, nachdem Sie verlagern das Ergebnis wieder nach unten.
InformationsquelleAutor bryan
Für einige algorithmen, die Sie brauchen eine konsistente bias bei der 'nächste' ist eine Band.
Dieser arbeitet unabhängig von den Vorzeichen von Zähler oder Nenner.
Wenn Sie möchten, um die übereinstimmung der Ergebnisse von
round(N/(double)D)
(Fließkomma-division und Rundung), hier sind ein paar Variationen, die alle produzieren die gleichen Ergebnisse:Hinweis: Die relative Geschwindigkeit von
(abs(d)>>1)
vs.(d/2)
wahrscheinlich ist Plattform abhängig.int
.By the way, wenn Sie geschehen, zu dividieren durch eine Potenz von zwei ist (das impliziert auch einen positiven divisor), können Sie die Vorteile der Tatsache, dass signed-shift-Rechte hat den Effekt der division mit Runde-Richtung negativ unendlich (im Gegensatz zu den divisionsoperator, die Runden in Richtung null) zu vermeiden, die Verwendung von bedingten Logik. Also die Formel wird
return (n+(1<<shift>>1))>>shift;
, was vereinfacht zu der form(n+C)>>shift
(woC=(1<<shift>>1)
wennshift
passiert, konstant sein.Die "mid-Wert bias" Sorge bezieht sich nur auf den Fall von genau 0.5 zwischen ganzen zahlen, so ist die esoterische sicher zu sein. Für eine Art der grafischen Darstellung, zum Beispiel, möchten Sie vielleicht, um zu sehen, Kontinuität um den Nullpunkt statt Symmetrie.
InformationsquelleAutor nobar
Folgende korrekt rundet den Quotienten auf die nächste Ganzzahl für positive und negative Operanden OHNE floating point oder bedingten Verzweigungen (siehe Montage-Ausgang unten). Nimmt N-bit-2er-Komplement-Ganzzahlen.
Den Wert der RUNDUNG haben das gleiche Vorzeichen wie der dividend (x) und die Hälfte der Größenordnung der divisor (y). Hinzufügen RUNDUNG auf die Dividende, so erhöht sich dessen Größe vor der integer-division schneidet die resultierende quotient. Hier ist die Ausgabe des gcc-Compilers mit -O3-Optimierung für ein 32-bit-ARM-Cortex-M4-Prozessor:
InformationsquelleAutor Dan Lewis
Einige alternativen für die division durch 4
Oder im Allgemeinen, die division durch eine beliebige Potenz von 2
Es funktioniert durch die Rundung nach oben, wenn der gebrochene Teil ⩾ 0.5, d.h. die erste Ziffer ⩾ base/2. Im Binär-es ist gleichbedeutend mit der addition der ersten fractional bit, um das Ergebnis
Diese Methode hat einen Vorteil in Architekturen mit einem flag-register, da das carry-flag enthält das letzten bit, das wurde verschoben aus. Zum Beispiel auf x86-kann es sein, optimiert in
Es ist auch leicht erweitert, um support-Ganzzahlen mit Vorzeichen. Beachten Sie, dass der Ausdruck für negative zahlen ist
können wir machen, damit es funktioniert für positive und negative Werte mit
InformationsquelleAutor phuclv
Lief ich in die gleichen Schwierigkeiten.
Der folgende code sollte funktionieren für positive ganze zahlen sind.
Habe ich noch nicht kompiliert ihn aber noch nicht getestet habe ich den Algorithmus auf einer google-Tabelle (ich weiß, wtf) und es hat funktioniert.
if(denominator == 1) return numerator;
. Was ist Ihr Zweck?InformationsquelleAutor Frank
Sicherer C-code (es sei denn, Sie haben andere Methoden der Behandlung /0):
return (_divisor > 0) ? ((_dividend + (_divisor - 1)) /_divisor) : _dividend;
Diese nicht mit den Problemen, die auftreten, von einem falschen Rückgabewert als Ergebnis Ihrer ungültige Eingabedaten, natürlich.
InformationsquelleAutor radsdau