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

Ich habe 3 base-Darstellungen für positive ganze zahlen:

Dezimal, in unsigned long-variable (z.B. unsigned long int NumDec = 200).
Hex in string-variable (z.B. string NumHex = "C8")
Binäre string-variable (z.B. string NumBin = "11001000")

Ich möchte in der Lage zu konvertieren zwischen zahlen in allen 3 Darstellungen in der meisten effizienten Art und Weise. I. e. zur Umsetzung der folgenden 6 Funktionen:

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 steigern.

Edit: Von "Effizienz" meine ich Zeit-Effizienz: Kürzeste Ausführungszeit.

Du bist die erste Funktion zwei Namen sind extrem irreführend. Du bist nicht der Rückkehr eine dezimale Darstellung. Die Sie zurückgeben, unsigned long, mit einer unbestimmten, opaken (es sei denn, Sie tun etwas Implementierung-definiert) interne Darstellung.
Was würden Sie vorschlagen, die Funktionsnamen zu werden?
Binary2Int und Hex2Int macht viel mehr Sinn. Natürlich werden diese Funktionen nicht gebraucht, mit strtol in der c-Bibliothek.
Binary2ULong und HexToULong wäre viel besser.
Der Grund, warum es verwirrend ist, dass numerische Datentypen, die nicht über eine Basis, und sind damit keine "Basis 10".

InformationsquelleAutor Igor Oks | 2009-05-04

binary c c++decimal hex

8

Wie andere haben darauf hingewiesen, ich würde beginnen mit sscanf(), printf() und/oder strtoul(). Sie sind schnell genug für die meisten Anwendungen, und Sie sind weniger wahrscheinlich, um die bugs. Ich will sagen, jedoch, dass diese Funktionen sind generisch, als Sie vielleicht erwarten, als Sie haben, um mit nicht-ASCII-Zeichensätze, die mit zahlen in jeder Basis und so weiter. Für einige domains ist es möglich, schlagen Sie die library-Funktionen.

So, erste Maßnahme, und wenn die Leistung von dieser Umwandlung ist wirklich ein Problem, dann:

1) In einigen Anwendungen /domains bestimmte Nummern erscheinen sehr oft, zum Beispiel null, 100, 200, 19.95, können so verbreitet, dass es Sinn macht zu optimieren Ihrer Funktionen zum konvertieren solcher zahlen mit ein paar if () - Anweisungen, und fallen dann wieder auf die generic library-Funktionen.
2) Verwenden Sie eine Tabelle, lookup, wenn die häufigsten 100 zahlen, und fallen dann wieder auf eine library-Funktion. Denken Sie daran, dass große Tische passen nicht in den cache und erfordert möglicherweise mehrere indirections für gemeinsam genutzte Bibliotheken, so Messen diese Dinge sorgfältig zu vergewissern, dass Sie nicht nachlassender Leistung.

Möglicherweise möchten Sie auch zu schauen, boost lexical_cast Funktionen, aber in meiner Erfahrung sind letztere relativ im Vergleich zu den guten alten C-Funktionen.

Hart, viele haben es gesagt, es lohnt sich, immer wieder zu wiederholen: "nicht optimieren diese Konvertierungen, bis Sie Beweise haben, dass er ein problem. Wenn Sie tun, optimieren, Messen Sie Ihre neue Implementierung, um sicherzustellen, es ist schneller und stellen Sie sicher, Sie haben eine Tonne von unit-tests für Ihre eigene version, weil Sie die Einführung bugs 🙁

InformationsquelleAutor coryan
4

Ich würde einfach vorschlagen mit sprintf und sscanf.

Auch, wenn du daran interessiert bist, wie es implementiert ist, können Sie einen Blick auf die source code für glibc, die GNU C-Bibliothek.
- Würde es nicht funktionieren langsamer als die anderen Lösungen?
- Zwei Antworten: 1. Testen Sie alle Lösungen und sehen, welche schneller ist. 2. Denken Sie daran, den code in die C Standard-Bibliothek ist in der Regel sachverständig geschrieben und hoch optimierte - Probleme wie diese sind der ganze Grund standard-Bibliotheken vorhanden, so haben die Programmierer den Zugang zu fachmännisch geschrieben, Lösungen für extrem häufige Probleme und don ' T haben zu gehen und ständig das Rad neu erfinden sich selbst.
- Denken Sie auch daran, dass sprintf und sscanf haben ausführlich getestet, und nicht gehen, um die kleinen bugs, die Sie führen könnten versuchen, um die Konvertierung selbst.
- Leider, %b ist nicht ein standard-printf umwandlungsspezifikator für binäre. Ich würde noch überlegen, es zu verwenden, obwohl.
InformationsquelleAutor Robert S. Barnes
3

Warum tun diese Routinen werden so Zeit-effizient? Diese Art von Behauptung macht mich immer Wunder. Sind Sie sicher, dass die offensichtliche Bekehrung Methoden wie strtol() zu langsam ist, oder dass Sie es besser machen können? System-Funktionen sind in der Regel ziemlich effizient. Sie sind manchmal langsamer zu unterstützen Allgemeingültigkeit und error-checking, aber Sie müssen überlegen, was zu tun mit Fehler. Wenn ein bin argument hat andere Zeichen als '0' und '1' sind, was dann? Abort? Propagieren massive Fehler?

Warum verwenden Sie "Dec", Sie repräsentieren die interne Darstellung? Dez, Hex und Bin-sollte verwendet werden, um beziehen sich auf den string-Repräsentationen. Es gibt nichts dezimal über eine unsigned long. Sind Sie den Umgang mit strings, die die Anzahl in dezimal? Wenn nicht, Sie sind verwirrend, die Menschen hier und werden viele verwirren mehr.

Die Umwandlung zwischen Binär-und hex-text-Formate können schnell und effizient durchgeführt werden, mit lookup-Tabellen, aber alles was mit dezimal-text-format wird komplizierter.

InformationsquelleAutor David Thornley
2

Hängt davon ab, was man optimieren, was meinst du mit "effizient"? Ist es wichtig, dass die Konvertierungen schnell, verbrauchen wenig Speicher, wenig Programmierer Zeit, weniger WTFs von anderen Programmierern Lesen Sie den code, oder was?

Für die Lesbarkeit und die Einfachheit der Implementierung, sollten Sie zumindest die Umsetzung Dec2Hex() und Dec2Binary() einfach mitgehen strotul(). Das macht Sie in one-Liner, die sehr effizient für zumindest einige der oben genannten Interpretationen des Wortes.
- Von "Effizienz" meine ich Zeit-Effizienz: Kürzeste Ausführungszeit. Vielen Dank für die Klarstellung, dass.
InformationsquelleAutor unwind
1

Klingt sehr nach einer Hausaufgabe problem, aber was solls...

Die kurze Antwort ist für die Konvertierung von long int zu deinen strings verwenden zwei lookup-Tabellen. Jede Tabelle sollte über 256 Einträge. Eine Karten ein byte in einen hex-string: 0 -> "00", 1 -> "01" usw. Die anderen Karten ein byte in ein bit-string: 0 -> "00000000", 1 -> "00000001".

Dann für jedes byte in Ihre long-int-du musst halt schauen, bis Sie die richtige Zeichenfolge, und verketten Sie Sie.

Konvertieren von Zeichenfolgen zurück zu lang, können Sie einfach konvertieren des hex-string und den bit-string zurück in eine dezimale Zahl durch die Multiplikation der numerische Wert der einzelnen Zeichen, indem Sie die entsprechende Leistung von 16 oder 2, und summieren der Ergebnisse.

EDIT: Du kannst auch das gleiche lookup-Tabellen für rückwärts-Konvertierung durch machen binäre Suche zum finden der richtigen Zeichenfolge. Dies würde log(256) = 8 Vergleiche der Saiten. Leider habe ich keine Zeit, um die Analyse zu tun, ob vergleichen von strings wäre viel schneller als die Multiplikation und die addition ganzer zahlen.
- In Bezug auf die Saiten zu lange Umbau: Würde es schneller arbeiten als strotul() ?
- Weiß nicht... Probieren Sie es.
InformationsquelleAutor Dima
1

Denke mal über die Hälfte der Aufgabe, für einen moment - die Umwandlung von einem string-Varianten Basis n long-Typ ohne Vorzeichen, wobei n eine Potenz von 2 ist (base 2 für Binär-und base-16 für hex).

Wenn Sie Ihre Eingabe ist gesund, dann wird diese Arbeit nicht mehr als ein vergleichen, ein subract, eine Verschiebung und eine oder pro digit. Wenn Sie Ihre Eingabe ist nicht gesund, gut, das ist, wo es häßlich, nicht wahr? Gerade die Umstellung superfast ist nicht schwer. Tun Sie es unter allen Umständen gut ist die Herausforderung.

Gehen wir also davon aus, dass Ihre Eingabe ist gesund, dann wird das Herz der Konvertierung ist:
```
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, wie einfach das ist? Und es wird nicht auf nicht-gesund-Eingänge. Die meisten Ihrer Arbeit wird zu gehen in die Herstellung Ihrer Eingabe sane, nicht die Leistung.

Nun, dieser code nutzt den Vorteil der Leistung von zwei verschieben. Es ist leicht zu erweitern-Basis-4, Basis 8, Basis 32, usw. Es funktioniert nicht bei nicht-Leistung der zwei Basen. Für diejenigen, die Ihre Mathematik zu ändern. Sie erhalten
```
val = (val * base) + digit
```
ist konzeptionell das gleiche für diese Gruppe von Operationen. Die Multiplikation mit der Basis Los ist äquivalent zu der Verschiebung. Also ich würde mich da eher um eine voll Allgemeine routine statt. Sie und desinfizieren Sie den code während der Hygienisierung der Eingänge. Und an diesem Punkt, strtoul ist wahrscheinlich Ihre beste Wette. Hier ist ein link zu eine version von strtoul. Fast alle arbeiten ist der Umgang mit Rand-Bedingungen - das sollte man in Ahnung, wo Sie Energien konzentriert werden sollten: richtig, belastbar-code. Die Einsparungen für die Verwendung von bit-Verschiebungen wird minimal sein im Vergleich zu den Einsparungen sagen, ohne Absturz auf schlechten Eingang.

InformationsquelleAutor plinth

Warum nicht einfach ein Makro, verwenden um auch das format als input. Wenn Sie in C mindestens.

#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);

Oder verwenden Sie sprintf direkt: Oder Sie können mehrere macroes.

#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 );

InformationsquelleAutor eaanon01

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.