Der effizienteste Weg, eine Zahl umzukehren

Lesezeit: 4 Minuten

Benutzer-Avatar
tommyk

Ich suche nach einem effizienten Algorithmus, um eine Zahl umzukehren, z

Eingang: 3456789

Ausgabe: 9876543

In C++ gibt es viele Optionen mit Verschiebungen und Bitmasken, aber was wäre der effizienteste Weg?

Meine Plattform: x86_64

Nummernbereich: XXX – XXXXXXXXXX (3 – 9 Ziffern)

BEARBEITEN
Die letzte Ziffer meiner Eingabe wird niemals eine Null sein, daher gibt es kein Problem mit führenden Nullen.

  • Wenn Sie es nicht als Zahl behandeln, warum lesen Sie es nicht einfach als Zeichenfolge? Das Umkehren ist dann trivial.

    Benutzer743382

    12. März 2013 um 6:55 Uhr

  • @hvd Dies würde Aufrufe von String-Konstruktor, Zuweisungsoperator, Destruktor verursachen … Ich bin mir nicht sicher, ob dies der effizienteste Weg ist.

    – Tommyk

    12. März 2013 um 6:59 Uhr

  • Möchten Sie führende Nullen? Beide Antworten schlagen für Fälle mit führenden Nullen fehl.

    – Raptz

    12. März 2013 um 7:00 Uhr

  • Brauchen Sie wirklich „den effizientesten Weg“? Ist dies wirklich der Ort, an dem die gesamte Verarbeitungszeit in Ihrem Programm verbracht wird? Klingt für mich nach verfrühter Optimierung.

    – Matthew Strawbridge

    12. März 2013 um 7:05 Uhr

  • Verschiebung und Bitmasken? Nicht in Basis 10. Wenn Sie dies in Basis 16 tun wollten, hätte ich ein paar nette Tricks im Ärmel, aber Binärcomputer mögen Basis 10 einfach nicht.

    – Harald

    12. März 2013 um 12:07 Uhr

So etwas wird funktionieren:

#include <iostream>

int main()
{
    long in = 3456789;
    long out = 0;
    while(in)
    {
        out *= 10;
        out += in % 10;
        in /= 10;
    }
    std::cout << out << std::endl;
    return 0;
}

  • @ H2CO3 Diese Antwort ist wirklich sehr häufig. Nicht sehr hart oder beeindruckend genug, um kopiert zu werden.

    – Raptz

    12. März 2013 um 6:59 Uhr

  • @ H2CO3 nein, ich habe eigentlich separat geschrieben

    – Stefan Lin

    12. März 2013 um 6:59 Uhr

  • @H2CO3 – Hm, ich habe auf Ihre Antwort geantwortet, aber Sie scheinen Ihre Antwort gelöscht zu haben. Ich habe meine positive Bewertung nur vorübergehend entfernt, weil mir klar wurde, dass ich math.stackexchange.com recherchieren sollte, falls eine effizientere Lösung gefunden wird (z.B eine Ein-Schritt-Formel) existierte. Aber die Mathematiker dort haben sich nichts dergleichen einfallen lassen, nur eine kompakte Form des Algorithmus, den Sie (und Stephen Lin) geschrieben haben. Also, Upvote im Geiste wiederhergestellt.

    – Schlappschwanz

    12. März 2013 um 7:03 Uhr

  • @acheong87 Danke. Ich habe meine Antwort entfernt, da sie sich als falsch herausstellte, genau wie diese. Es zählt keine nachgestellten Nullen, XYZ0 wird ZYX Anstatt von 0ZYX.

    Benutzer529758

    12. März 2013 um 7:05 Uhr

  • @ H2CO3 Es macht mir nichts aus, dies auch zu notieren, aber es ist nicht klar, was OP will, da er Bitverschiebungen und dergleichen erwähnt (also will er vermutlich eher eine numerische als eine Zeichenfolgendarstellung).

    – Stefan Lin

    12. März 2013 um 7:07 Uhr


#include <stdio.h>
unsigned int reverse(unsigned int val)
{
 unsigned int retval = 0;

 while( val > 0)
 {
     retval  = 10*retval + val%10;
     val     /= 10;
 }
 printf("returning - %d", retval);
 return retval;
}


int main()
{
    reverse(123);
}

Sie können die Zahl in eine Zeichenfolge konvertieren und die Zeichenfolge dann mit STL-Algorithmen umkehren. Der folgende Code sollte funktionieren:

 long number = 123456789;
 stringstream ss;
 ss << number;
 string numberToStr = ss.str();

 std::reverse(numberToStr.begin(), numberToStr.end());

 cout << atol(numberToStr.c_str());

Möglicherweise müssen Sie diese relevanten Header-Dateien einschließen. Ich bin mir nicht sicher, ob es der effizienteste Weg ist, aber STL-Algorithmen sind im Allgemeinen sehr effizient.

static public int getReverseInt(int value) {
    int resultNumber = 0;
    for (int i = value; i != 0;) {
        int d = i / 10;
        resultNumber = (resultNumber - d) * 10 + i;
        i = d;
    }
    return resultNumber;
}

Ich denke, dies wird die schnellstmögliche Methode ohne Verwendung sein asm. Beachten Sie, dass d*10 + i ist äquivalent zu i%10 aber viel schneller, da Modulo etwa 10-mal langsamer ist als die Multiplikation.
Ich habe es getestet und es ist etwa 25 % schneller als andere Antworten.

Benutzer-Avatar
Pratiush Prasunn

int ans=0;
int rev(int n)
{
  ans=(ans+(n%10))*10; // using recursive function to reverse a number;
  if(n>9) 
    rev(n/10);
}

int main()
{
  int m=rev(456123); // m=32
  return 0;
}

  • ist es der effizienteste Weg, dies zu tun?

    – Hariom Singh

    12. August 2017 um 18:18 Uhr

  • Nicht im Hinblick auf das Gedächtnis, aber praktisch beim Lösen von Problemen 🙂

    – Pratiush Prasunn

    13. August 2017 um 15:44 Uhr

Benutzer-Avatar
Roshan

 //Recursive method to find the reverse of a number  
 #include <bits/stdc++.h> 
    using namespace std; 
    int reversDigits(int num) 
    { 
    static int rev_num = 0; 
    static int base_pos = 1; 
    if(num > 0) 
    { 
        reversDigits(num/10); 
        rev_num += (num%10)*base_pos; 
        base_pos *= 10; 
    } 
    return rev_num; 
    } 
    int main() 
    { 
        int num = 4562; 
        cout << "Reverse  " << reversDigits(num); 
    } ``

  • ist es der effizienteste Weg, dies zu tun?

    – Hariom Singh

    12. August 2017 um 18:18 Uhr

  • Nicht im Hinblick auf das Gedächtnis, aber praktisch beim Lösen von Problemen 🙂

    – Pratiush Prasunn

    13. August 2017 um 15:44 Uhr

Benutzer-Avatar
mufeez-shaikh

// recursive method to reverse number. lang = java
static void reverseNumber(int number){
    // number == 0 is the base case
    if(number !=0 ){
        //recursive case
        System.out.print(number %10);
        reverseNumber(number /10);
    }
}

1019090cookie-checkDer effizienteste Weg, eine Zahl umzukehren

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

Privacy policy