Wie finde ich das nächste Vielfache von 10 einer ganzen Zahl?

Lesezeit: 9 Minuten

Benutzeravatar von TTT
TTT

Eine dynamische Ganzzahl ist eine beliebige Zahl zwischen 0 und 150.

dh – Zahl gibt 41 zurück, muss 50 zurückgeben. Wenn Zahl 10 ist, muss 10 zurückgegeben werden. Zahl ist 1, muss 10 zurückgegeben werden.

Dachte, ich könnte die Deckenfunktion verwenden, wenn ich die Ganzzahl als Dezimalzahl ändere …? Verwenden Sie dann die Deckenfunktion und setzen Sie sie auf Dezimal zurück.
Die einzige Sache ist, dass man auch wissen müsste, ob die Nummer 1, 2 oder 3 Ziffern ist (dh – 7 vs. 94 vs. 136)

Gibt es einen besseren Weg, dies zu erreichen?

Danke,

  • Um etwas zu klären, was mehrere Leute kommentiert haben, beachten Sie bitte, dass die Domäne dieser Funktion auf die ganzen Zahlen 0-150 beschränkt ist.

    – bta

    8. März 2010 um 20:01 Uhr

  • Ich verstehe nicht, wofür diese einfache Frage so viele Stimmen bekommt. Ist es wirklich so ein Denksport?

    – Lukas Rahne

    8. März 2010 um 21:12 Uhr

  • @ralu: Die einfachsten Fragen bekommen hier immer die positiven Stimmen, weil sich nur sehr wenige Leute mit den schwierigen beschäftigen.

    – BlueRaja – Danny Pflughöft

    8. März 2010 um 22:33 Uhr

  • Mögliches Duplikat von C++: Aufrunden auf das nächste Vielfache einer Zahl

    – phuklv

    13. Juli 2018 um 2:04 Uhr

Benutzeravatar von R Samuel Klatchko
R. Samuel Klatschko

n + (10 - n % 10)

Wie das funktioniert. Der %-Operator wertet den Rest der Division aus (so 41 % 10 wertet zu 1 aus, während 45 % 10 wertet zu 5). Das Subtrahieren von 10 ergibt, wie viel Sie benötigen, um das nächste Vielfache zu erreichen.

Das einzige Problem ist, dass dadurch aus 40 50 wird. Wenn Sie das nicht möchten, müssen Sie ein Häkchen hinzufügen, um sicherzustellen, dass es nicht bereits ein Vielfaches von 10 ist.

if (n % 10)
    n = n + (10 - n % 10);

  • Ah, das ist schneller als meiner.

    – Harvey

    8. März 2010 um 18:23 Uhr

  • @Harvey: Es ist ratsam, keine Leistungsangaben zu machen, bis Sie sie gemessen haben. Der Compiler ist wahrscheinlich klüger als wir alle.

    – Greg Hewgill

    8. März 2010 um 18:37 Uhr

  • Warum nicht (n+9) - ((n+9)%10) ? Dies funktioniert auch für Vielfache von 10 und erfordert immer noch nur drei Operationen.

    – Mark Dickinson

    8. März 2010 um 18:48 Uhr

  • Es gibt eine viel einfachere Lösung weiter unten auf der Seite. n = (n+9)/10.

    – Stefan Kendall

    8. März 2010 um 19:26 Uhr

  • Dies ist eine der schlechtesten Optionen. Es gibt keinen Grund, dafür eine bedingte Verzweigung zu verwenden. Das macht schlechterer Code als die meisten anderen anständigen Vorschläge

    – Peter Cordes

    3. März 2016 um 8:40 Uhr

AnT steht mit Russlands Benutzer-Avatar
AnT steht zu Russland

Sie können dies tun, indem Sie eine ganzzahlige Division durch 10 durchführen Aufrundenund dann das Ergebnis mit 10 multiplizieren.

Zu teilen A durch B aufrunden, addieren B - 1 zu A und dividiere es dann durch B mit “gewöhnlicher” ganzzahliger Division

Q = (A + B - 1) / B 

Für Ihr spezifisches Problem sieht das While-Ding zusammen wie folgt aus

A = (A + 9) / 10 * 10

Das wird “einrasten” A zum nächstgrößeren Vielfachen von 10.

Die Notwendigkeit für die Division und für die Ausrichtung kommt so oft vor, dass ich normalerweise in meinen Programmen Makros zum Teilen hätte [unsigned] Ganzzahlen mit Rundung

#define UDIV_UP(a, b) (((a) + (b) - 1) / (b))

und zum Ausrichten einer ganzen Zahl an der nächsten Grenze

#define ALIGN_UP(a, b) (UDIV_UP(a, b) * (b))

was das obige so aussehen lassen würde

A = ALIGN_UP(A, 10);

PS Ich weiß nicht, ob Sie dies auf negative Zahlen erweitern müssen. Wenn Sie dies tun, sollten Sie darauf achten, es richtig zu machen, je nachdem, was Sie als Ergebnis benötigen.

  • +1 Dies ist bisher die einzige ganzzahlige arithmetische Lösung, die tatsächlich funktioniert, wenn n = 10 ohne einen zusätzlichen bedingten Test.

    – Greg Hewgill

    8. März 2010 um 18:27 Uhr


  • Nun, das ist eigentlich eine ziemlich bekannte und weit verbreitete Redewendung. Ich bin überrascht, dass ich es als erster erwähnt habe.

    – AnT steht zu Russland

    8. März 2010 um 18:39 Uhr

  • Ich auch. Ich bin überrascht, wie viele Antworten es tatsächlich gab falsch zu beginnen (der n = 10-Fall wurde auch ausdrücklich in der Frage erwähnt).

    – Greg Hewgill

    8. März 2010 um 18:43 Uhr

  • Wie überprüfe ich den Überlauf?

    – Benutzer426

    29. November 2021 um 11:01 Uhr

Benutzeravatar von bta
bta

Wie wäre es mit ((n + 9) / 10) * 10 ?

Ergibt 0 => 0, 1 => 10, 8 => 10, 29 => 30, 30 => 30, 31 => 40

  • Dies scheint die einfachste Lösung zu sein.

    – Stefan Kendall

    8. März 2010 um 19:25 Uhr

  • Äh… (n + 9) / 10 Erträge 8 => 1nicht 8 => 10 wie du in deinem Post beschreibst. Du hast wahrscheinlich vergessen, das Ergebnis wieder mit zu multiplizieren 10.

    – AnT steht zu Russland

    8. März 2010 um 19:38 Uhr


  • +1: Gute Antwort. Ich habe es kürzlich in einer Bitset-Implementierung verwendet. F: Wenn ein Wort 32 Bits enthalten kann, wie viele Wörter sind dann erforderlich, um ‘n’ Bits (n>=0) zu halten? A: (n+31)/32

    – Arun

    10. März 2010 um 1:03 Uhr

Benutzeravatar von Peter Cordes
Peter Kordes

tl;dr: ((n + 9) / 10) * 10 kompiliert in mehr Fällen zum schönsten (schnellsten) ASM-Codeund ist für Leute, die wissen, was die Ganzzahldivision in C tut, leicht zu lesen und zu verstehen. Es ist eine ziemlich verbreitete Redewendung.

Ich habe nicht untersucht, was die beste Option für etwas ist, das mit Negativ arbeiten muss nda Sie je nach Anwendung möglicherweise von Null weg runden möchten, anstatt immer noch in Richtung +Unendlich.


Wenn man sich die C-Operationen ansieht, die von den verschiedenen Vorschlägen verwendet werden, ist die leichteste von Mark Dickinson (in Kommentaren):

(n+9) - ((n+9)%10)

Es sieht effizienter aus als das einfache Teilen / Multiplizieren, das von ein paar Leuten (einschließlich @bta) vorgeschlagen wird: ((n + 9) / 10) * 10, weil es nur eine Addition statt einer Multiplikation hat. (n+9 ist ein gemeinsamer Teilausdruck, der nur einmal berechnet werden muss.)

Es stellt sich heraus, dass beide mit dem Compiler-Trick des Konvertierens zu buchstäblich identischem Code kompiliert werden Division durch eine Konstante in ein Multiplizieren und Verschieben, siehe diese Fragen und Antworten, um zu erfahren, wie es funktioniert. Im Gegensatz zu einer Hardware div Anweisung, die gleich viel kostet, egal ob Sie den Quotienten, den Rest oder beide Ergebnisse verwenden, erfordert die mul/shift-Methode zusätzliche Schritte, um den Rest zu erhalten. Der Compiler erkennt also, dass er mit einer billigeren Berechnung dasselbe Ergebnis erzielen kann, und kompiliert am Ende beide Funktionen in denselben Code.

Dies gilt weiter x86, PPC und ARM, und all die anderen Architekturen, die ich mir im Godbolt-Compiler-Explorer angesehen habe. In der ersten Version dieser Antwort sah ich eine sdiv für die %10 auf Godbolts gcc4.8 für ARM64, aber es ist nicht mehr installiert (vielleicht weil es falsch konfiguriert wurde?) ARM64 gcc5.4 macht das nicht.

Godbolt hat jetzt MSVC (CL) installiert, und einige dieser Funktionen werden anders kompiliert, aber ich habe mir nicht die Zeit genommen, zu sehen, welche besser kompiliert werden.


Beachten Sie, dass in der gcc-Ausgabe für x86 die Multiplikation mit 10 billig ist lea eax, [rdx + rdx*4] dann n*5 machen add eax,eax das zu verdoppeln. imul eax, edx, 10 hätte auf Intel Haswell eine um 1 Zyklus höhere Latenz, wäre aber kürzer (eine uop weniger). gcc / clang benutze es nicht einmal mit -Os -mtune=haswell :/


Die akzeptierte Antwort (n + 10 - n % 10) ist noch billiger zu berechnen: n+10 kann parallel passieren n%10, sodass die Abhängigkeitskette einen Schritt kürzer ist. Es wird zu einer Anweisung weniger kompiliert.

Jedoches gibt die falsche Antwort für Vielfache von 10: zB 10 -> 20. Der vorgeschlagene Fix verwendet eine if(n%10) zu entscheiden, ob ich etwas tun soll. Dies kompiliert in a cmov, also ist es länger und schlimmer als der Code von @Bta. Wenn Sie eine Bedingung verwenden, tun Sie dies, um vernünftige Ergebnisse für negative Eingaben zu erhalten.


So verhalten sich alle vorgeschlagenen Antworten, auch bei negativen Eingaben:

./a.out | awk -v fmt="\t%4s" '{ for(i=1;i<=NF;i++){ a[i]=a[i] sprintf(fmt, $i); } } END { for (i in a) print a[i]; }'
       i     -22     -21     -20     -19     -18     -12     -11     -10      -9      -8      -2      -1       0       1       2       8       9      10      11      12         18      19      20      21      22
    mark     -10     -10     -10     -10       0       0       0       0       0       0       0       0       0      10      10      10      10      10      20      20         20      20      20      30      30
    igna     -10     -10     -10       0       0       0       0       0      10      10      10      10      10      10      10      10      10      20      20      20         20      20      30      30      30
    utaal    -20     -20     -20     -10     -10     -10     -10     -10       0       0       0       0       0      10      10      10      10      10      20      20         20      20      20      30      30
     bta     -10     -10     -10     -10       0       0       0       0       0      10      10      10      10      10      10      10      10      10      20      20         20      20      20      30      30
    klatchko -10     -10     -10     -10       0       0       0       0       0       0       0       0       0      10      10      10      10      10      20      20         20      20      20      30      30
    branch   -10     -10     -20       0       0       0       0     -10      10      10      10      10       0      10      10      10      10      10      20      20         20      20      20      30      30

(awk-Programm transponieren)

Ignacios n + (((9 - (n % 10)) + 1) % 10) funktioniert “korrekt” für negative ganze Zahlen, rundet in Richtung + Unendlich, ist aber viel teurer zu berechnen. Es erfordert zwei Modulo-Operationen, ist also im Wesentlichen doppelt so teuer. Es kompiliert zu etwa doppelt so vielen x86-Anweisungen und erledigt etwa die doppelte Arbeit der anderen Ausdrücke.

Ergebnisdruckprogramm (dasselbe wie die Godbolt-Links oben)

#include <stdio.h>
#include <stdlib.h>

int f_mark(int n) { return (n+9) - ((n+9)%10); }                   // good
int f_bta(int n) { return ((n + 9) / 10) * 10; }                   // compiles to literally identical code

int f_klatchko(int n) { return n + 10 - n % 10; }                  // wrong, needs a branch to avoid changing multiples of 10
int f_ignacio(int n) { return n + (((9 - (n % 10)) + 1) % 10); }   // slow, but works for negative
int roundup10_utaal(int n) {  return ((n - 1) / 10 + 1) * 10; }

int f_branch(int n) { if (n % 10) n += (10 - n % 10); return n; }  // gcc uses cmov after f_accepted code

int main(int argc, char**argv)
{
    puts("i\tmark\tigna\tutaal\tbta\tklatch\tbranch");
    for (int i=-25 ; i<25 ; i++)
    if (abs(i%10) <= 2 || 10 - abs(i%10) <= 2)  // only sample near interesting points
        printf("%d\t%d\t%d\t%d\t%d\t%d\t%d\n", i, f_mark(i), f_accepted(i),
           f_ignacio(i), roundup10_utaal(i), f_bta(i), f_branch(i));
}

Harveys Benutzeravatar
Harvey

Wie wäre es mit ganzzahliger Mathematik:

N=41
N+=9   // Add 9 first to ensure rounding.
N/=10  // Drops the ones place
N*=10  // Puts the ones place back with a zero

  • Entspricht nicht den Anforderungen des OP.

    – Matthäus Flaschen

    8. März 2010 um 18:23 Uhr

  • das wird den Boden berechnen, um die Decke zu erhalten, addieren Sie zuerst 9

    – Kobbeln

    8. März 2010 um 18:23 Uhr

in C, Einzeiler:

int inline roundup10(int n) {
  return ((n - 1) / 10 + 1) * 10;
}

  • Entspricht nicht den Anforderungen des OP.

    – Matthäus Flaschen

    8. März 2010 um 18:23 Uhr

  • das wird den Boden berechnen, um die Decke zu erhalten, addieren Sie zuerst 9

    – Kobbeln

    8. März 2010 um 18:23 Uhr

Beachten Sie, dass Antworten basierend auf den div- und mod-Operatoren (“https://stackoverflow.com/” und “%”) ohne if-Test nicht für negative Zahlen funktionieren, da C und C++ diese Operatoren für negative Zahlen falsch implementieren . (-3 mod 5) ist 2, aber C und C++ berechnen (-3 % 5) als -3.

Sie können Ihre eigenen div- und mod-Funktionen definieren. Zum Beispiel,

int mod(int x, int y) {
  // Assert y > 0
  int ret = x % y;
  if(ret < 0) {
    ret += y;
  }
  return ret;
}

  • OP hat angegeben, dass diese Funktion nur mit den Zahlen 0-150 funktioniert.

    – bta

    8. März 2010 um 19:05 Uhr

1413140cookie-checkWie finde ich das nächste Vielfache von 10 einer ganzen Zahl?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy