konvertieren Effizientes zwischen Hex, Binär und Dezimal in C / C ++

StackOverflow https://stackoverflow.com/questions/819487

  •  03-07-2019
  •  | 
  •  

Frage

Ich habe 3 Basis Darstellungen für positive ganze Zahlen sind:

  1. Dezimal, in unsigned long Variable (z unsigned long int NumDec = 200 ).
  2. Hex, in String-Variable (z.B. string NumHex = "C8" )
  3. Binary, in String-Variablen (z string NumBin = "11001000" )

Ich möchte zwischen den Zahlen in allen drei Darstellungen auf die effizienteste Art und Weise konvertieren können. D. h die folgenden 6 Funktionen zu implementieren: 

unsigned long int Binary2Dec(const string & Bin) {}
unsigned long int Hex2Dec(const string & Hex) {}
string Dec2Hex(unsigned long int Dec) {}
string Binary2Hex(const string & Bin) {}
string Dec2Binary(unsigned long int Dec) {}
string Hex2Binary(const string & Hex) {}

Was ist der effizienteste Ansatz für jeden von ihnen? Ich kann mit C und C ++, aber nicht erhöhen.

Edit: Mit "Effizienz" Ich meine Zeiteffizienz: Kürzeste Ausführungszeit

.
War es hilfreich?

Lösung

Wie andere haben darauf hingewiesen, würde ich beginnen mit sscanf() , printf() und / oder strtoul() . Sie sind schnell genug für die meisten Anwendungen, und sie sind weniger wahrscheinlich, Fehler zu haben. Ich will aber sagen, dass diese Funktionen mehr generisch sind, als man erwarten könnte, da sie mit Nicht-ASCII-Zeichensätzen zu tun haben, mit Zahlen in jeder Basis dargestellt und so weiter. Für einige Domains ist es möglich, die Bibliotheksfunktionen zu schlagen.

Also, zuerst messen, und wenn die Leistung dieser Umwandlung ist wirklich ein Problem, dann:

1) Bei einigen Anwendungen / Domänen bestimmte Nummern sehr oft erscheinen, beispielsweise Null, 100, 200, 19.95, kann so häufig sein, dass es sinnvoll, Ihre Funktionen zu optimieren, macht ein solche Zahlen mit einem Bündel konvertieren von if () Aussagen und dann zurück auf die generischen Bibliotheksfunktionen fallen. 2) Verwenden Sie eine Tabellensuche, wenn die häufigsten 100 Nummern, und dann wieder auf einer Bibliotheksfunktion fallen. Denken Sie daran, dass große Tabellen nicht in den Cache passen kann und mehrere Umwege für gemeinsam genutzte Bibliotheken benötigt, so messen diese Dinge sorgfältig sicherstellen, dass Sie nicht die Leistung abnehmen.

Sie können auch auf Schub aussehen wollen lexical_cast Funktionen, obwohl in meiner Erfahrung ist diese relativ im Vergleich zu den guten alten C-Funktionen.

Tough viele hat es gesagt, es lohnt sich zu wiederholen immer und immer wieder: nicht optimiert diese Umwandlungen, bis Sie Beweise haben, dass sie ein Problem sind. Wenn Sie optimieren, messen Sie Ihre neue Implementierung sicherstellen, dass es schneller ist und stellen Sie sicher, Sie haben eine Tonne von Unit-Tests für Ihre eigene Version, weil Sie Fehler einführen: - (

Andere Tipps

würde ich vorschlagen, nur mit sprintf und sscanf .

Auch, wenn Sie daran interessiert sind, wie es umgesetzt ist kann man einen Blick auf die Quellcode für glibc, die GNU C Library .

Warum haben diese Routinen so zeiteffizient sein? Diese Art von Anspruch macht mich immer Wunder. Sind Sie sicher, dass die offensichtlichen Konvertierungsmethoden wie strtol () sind zu langsam, oder dass Sie es besser machen können? Systemfunktionen sind in der Regel ziemlich effizient. Sie sind manchmal langsamer zu unterstützen Allgemeinheit und Fehlerprüfung, aber Sie müssen sich überlegen, was mit Fehlern zu tun. Wenn ein bin Argument hat andere Zeichen als ‚0‘ und ‚1‘, was dann? Abbrechen? Propagieren massive Fehler?

Warum verwenden Sie „Dec“ die interne Darstellung zu vertreten? Dezember, Hex und Bin sollte auf die Stringdarstellungen beziehen verwendet werden. Es gibt nichts dezimal über eine unsigned long. Beschäftigen Sie Strings mit der Zahl in Dezimal zeigt? Wenn nicht, sind Sie Leute hier verwirrend und werden viel mehr verwirren.

Die Transformation zwischen Binär- und Hex-Text-Formaten schnell erledigt werden kann und effizient, mit Lookup-Tabellen, aber alles, was dezimal Textformat beteiligt sein wird komplizierter.

Das hängt davon ab, was Sie Optimierung für, was meinst du mit „effizient“? Ist es wichtig, dass die Umsätze schnell sein, verwenden Sie wenig Speicher, wenig Programmierer Zeit, weniger WTFs von anderen Programmierern Lesen des Codes , oder was?

Zur besseren Lesbarkeit und einfache Implementierung, sollten Sie zumindest implementieren sowohl Dec2Hex() und Dec2Binary() von nur strotul() aufrufen. Das macht sie in Einzeiler, die für zumindest einige der oben genannten Interpretationen des Wortes sehr effizient ist.

Klingt sehr ähnlich wie ein Hausaufgabe Problem, aber was zum Teufel ...

Die kurze Antwort ist für von long int Umwandlung in den Saiten zwei Lookup-Tabellen verwenden. Jede Tabelle sollte 256 Einträge haben. Man bildet ein Byte zu einem Hex-String: 0 -> "00", 1 -> "01" usw. Die andere bilden ein Byte zu einem Bitstring. 0 -> "00000000", 1 -> "00000001"

Dann für jedes Byte in Ihrer langen int man muss nur die richtige Zeichenfolge nachzuschlagen, und verketten sie.

von Strings zu konvertieren zurück lange Sie einfach den Hex-String umwandeln kann und die Bit-String zurück in eine Dezimalzahl durch den numerischen Wert jedes Zeichens durch die entsprechende Leistung von 16 oder 2, multipliziert und die Ergebnisse zusammen.

EDIT: Sie können auch die gleichen Lookup-Tabellen für die Abwärtsumwandlung verwenden, indem binäre Suche zu tun die richtige Zeichenfolge zu finden. Dies würde log (256) = 8 Vergleiche Ihrer Saiten. Leider habe ich keine Zeit, um die Analyse zu tun, ob die Strings Vergleich viel schneller sein würde als Multiplikation und das Hinzufügen von ganzen Zahlen.

Denken sie etwa die Hälfte der Aufgabe für einen Moment - aus einer String-ized Basis n zu unsigned long Umwandlung, wobei n eine Potenz von 2 ist (Basis 2 für binäre und Basis 16 für hex)

.

Wenn Sie Ihre Eingabe geistig gesund ist, dann ist diese Arbeit ist nichts anderes als ein Vergleich, eine subract, eine Verschiebung und einer oder pro Ziffer. Wenn Ihre Eingabe nicht gesund ist, na ja, das ist, wo es hässlich wird, nicht wahr? die Umwandlung super zu tun, ist nicht schwer. Tut es unter allen Umständen gut ist die Herausforderung.

Lassen Sie sich also davon ausgehen, dass Ihre Eingabe gesund ist, dann wird das Herz Ihrer Umwandlung ist dies: 

unsigned long PowerOfTwoFromString(char *input, int shift)
{
    unsigned long val = 0;
    char upperLimit = 'a' + (1 << shift)
    while (*input) {
        char c = tolower(*input++);
        unsigned long digit = (c > 'a' && c < upperLimit) ? c - 'a' + 10 : c - '0';
        val = (val << shift) | digit;
    }
    return val;
 }

 #define UlongFromBinaryString(str) PowerOfTwoFromString(str, 1)
 #define UlongFromHexString(str) PowerOfTwoFromString(str, 4)

Sehen Sie, wie einfach das ist? Und es wird auf nicht-sane Eingänge fehlschlagen. Die meisten Ihrer Arbeit gehen werden in der Herstellung Ihre Eingabe gesund, nicht die Leistung.

Nun nimmt dieser Code Vorteil der Leistung von zwei Schalt. Es ist einfach zu Boden 4, Basis 8, 32 Basis zu erweitern, usw. Es wird nicht auf Nicht-Leistung von zwei Basen arbeiten. Für diejenigen, muss Ihre mathematischen ändern. Sie erhalten 

val = (val * base) + digit

, das ist vom Konzept her das gleiche für diesen Satz von Operationen. Die Multiplikation mit der Basis wird sich die Verschiebung äquivalent zu sein. Also würde ich sein, wie wahrscheinlich eine ganz allgemeine Routine stattdessen zu verwenden. Und sanieren den Code, während die Eingänge Desinfizieren. Und an diesem Punkt ist strtoul wahrscheinlich die beste Wahl. Hier ist ein Link zu einer Version rel="nofollow von strtoul. Fast alle Arbeiten sind der Umgang mit Randbedingungen - das sollten Sie in Hinweis auf, wo man Energien sollen fokussiert werden: richtig, elastischen Code. Die Einsparungen für Bit-Verschiebungen unter Verwendung werden minimal sein, im Vergleich zu den Einsparungen in Höhe von etwa nicht auf schlechten Eingang abstürzt.

Warum nicht einfach ein Makro verwenden, um auch das Format als Eingabe verwenden. Wenn Sie in C zumindest sind. 

#define TO_STRING( string, format, data) \
sprintf( string, "##format##", data)
// Int
TO_STRING(buf,%d,i);
// Hex ( Two char representation )
TO_STRING(buf,%02x,i);
// Binary
TO_STRING(buf,%b,i);

Sie können auch sprintf direkt verwenden. Sie können auch mehrere macroes haben 

#define INT_STRING( buf, data) \
sprintf( buf, "%d", data)
#define HEX_STRING( buf, data) \
sprintf( buf, "%x", data)
#define BIN_TO_STRING( buf, data) \
sprintf( buf, "%b", data)

BIN_TO_STRING( loc_buf, my_bin );
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top