efficiente convertire tra Hex, binario e decimale in C/C++

Question

ho 3 rappresentazioni di base per i numeri interi positivi:

1. decimale, in variabile lungo senza segno (per esempio unsigned long int NumDec = 200).
2. Hex, in variabile stringa (ad esempio stringa NumHex = "C8")
3. binario, nella variabile stringa (ad esempio stringa NumBin = "11001000")

voglio essere in grado di convertire tra i numeri in tutte e 3 le rappresentazioni nel modo più efficiente. Cioè per implementare le seguenti 6 funzioni:

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) {} 

Qual è l'approccio più efficiente per ciascuna di esse? Posso usare C e C++, ma non aumentare.

Modifica: Per "efficienza" intendo efficienza temporale: il tempo di esecuzione più breve.

Answer 1

Come altri hanno sottolineato, vorrei iniziare con sscanf(), printf() e/o strtoul(). Sono abbastanza veloci per la maggior parte delle applicazioni e hanno meno probabilità di avere bug. Dirò, tuttavia, che queste funzioni sono più generiche di quanto ci si potrebbe aspettare, poiché devono trattare set di caratteri non ASCII, con numeri rappresentati in qualsiasi base e così via. Per alcuni domini è possibile battere le funzioni della libreria.

Quindi, misurare prima, e se le prestazioni di questi conversione è davvero un problema, allora:

1) In alcune applicazioni/domini determinati numeri appaiono molto spesso, ad esempio pari a zero, 100, 200, 19.95, può essere così comune che ha senso ottimizzare le vostre funzioni per convertire tali numeri con un gruppo di istruzioni if ​​() e poi ricorrere alle funzioni della libreria generica. 2) Utilizzare una ricerca tabella se i 100 numeri più comuni e quindi ricorrere a una funzione di libreria. Ricorda che le tabelle di grandi dimensioni potrebbero non rientrare nella tua cache e potrebbero richiedere più riferimenti indiretti per le librerie condivise, quindi misura attentamente queste cose per assicurarti di non ridurre le prestazioni.

Si potrebbe anche voler dare un'occhiata alle funzioni di lexical_cast, sebbene nella mia esperienza queste ultime siano relativamente paragonate alle buone vecchie funzioni C.

In molti hanno detto che vale la pena ripeterlo: non ottimizzare queste conversioni finché non si è certi che rappresentano un problema. Se ottimizzi, misura la tua nuova implementazione per assicurarti che sia più veloce e assicurati di avere un sacco di test unitari per la tua versione, perché introdurrai bug :-(

Answer 2

Dipende da cosa stai ottimizzando, cosa intendi con "efficiente"? È importante che le conversioni siano veloci, utilizza poca memoria, poco tempo per programmare, meno WTFs da altri programmatori che leggono il codice o cosa?

Per la leggibilità e la facilità di implementazione, è necessario almeno implementare sia Dec2Hex() e Dec2Binary() semplicemente chiamando strotul(). Ciò li rende in one-liner, che è molto efficace per almeno alcune delle suddette interpretazioni della parola.

Answer 3

suona molto come un problema di compiti a casa, ma che diamine ...

La risposta breve è per la conversione da long int sulle tue corde utilizzano due tabelle di ricerca. Ogni tabella dovrebbe avere 256 voci. Uno mappa un byte in una stringa esadecimale: 0 -> "00", 1 -> "01", ecc. L'altro mappa un byte in una stringa di bit: 0 -> "00000000", 1 -> "00000001".

Quindi per ogni byte del tuo long int devi solo cercare la stringa corretta e concatenarli.

Per convertire da stringhe a lunghe, è sufficiente convertire la stringa esadecimale e la stringa di bit in un numero decimale moltiplicando il valore numerico di ciascun carattere con la potenza appropriata di 16 o 2 e sommando i risultati.

MODIFICA: è anche possibile utilizzare le stesse tabelle di ricerca per la conversione all'indietro eseguendo la ricerca binaria per trovare la stringa corretta. Ciò richiederebbe log (256) = 8 confronti delle stringhe. Sfortunatamente non ho tempo per fare un'analisi se confrontare stringhe sarebbe molto più veloce della moltiplicazione e dell'aggiunta di interi.

Answer 4

Suggerirei di utilizzare solo sprintf e sscanf.

Inoltre, se sei interessato a come è implementato, puoi dare un'occhiata allo source code per glibc, the GNU C Library.

Answer 5

Perché non utilizzare solo una macro per prendere anche il formato come input. Se sei in C almeno.

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

Oppure si può usare sprintf direttamente: Oppure si può avere più 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); 

Answer 6

Perché queste routine devono essere così efficienti nel tempo? Questo tipo di affermazioni mi fa sempre meravigliare. Sei sicuro che i metodi di conversione ovvi come strtol() siano troppo lenti o che tu possa fare di meglio? Le funzioni di sistema sono in genere piuttosto efficienti. A volte sono più lenti a supportare la generalità e il controllo degli errori, ma è necessario considerare cosa fare degli errori. Se un argomento bin contiene caratteri diversi da "0" e "1", allora? Interrompere? Propagare errori enormi?

Perché stai utilizzando "Dec" per rappresentare la rappresentazione interna? Dec, Hex e Bin dovrebbero essere usati per fare riferimento alle rappresentazioni di stringa. Non c'è nulla di decimale riguardo a unsigned long. Hai a che fare con stringhe che mostrano il numero in decimale? Se no, stai confondendo le persone qui e ne confonderai molte altre.

La trasformazione tra formati di testo binario e esadecimale può essere eseguita in modo rapido ed efficiente, con tabelle di ricerca, ma tutto ciò che riguarda il formato del testo decimale sarà più complicato.

Answer 7

Pensiamo alla metà del compito per un momento: la conversione da una base di stringa n a una senza firma lunga, dove n è una potenza di 2 (base 2 per binario e base 16 per esadecimale).

Se il tuo input è sano, questo lavoro non è altro che un confronto, un surrogato, uno spostamento e un o per cifra. Se il tuo input non è sano, beh, è ​​lì che diventa brutto, vero? Fare la conversione superveloce non è difficile. Farlo bene in tutte le circostanze è la sfida.

Quindi diamo per scontato che il vostro ingresso è sano di mente, poi il cuore della vostra conversione è questo:

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) 

Vedere quanto facile che è? E fallirà su input non sani. La maggior parte del tuo lavoro sta andando a rendere il tuo input sensato, non le prestazioni.

Ora, questo codice sfrutta la potenza di due spostamenti. È facile estendere alla base 4, alla base 8, alla base 32, ecc. Non funzionerà sulla non potenza di due basi. Per quelli, la tua matematica deve cambiare. Otterrete

val = (val * base) + digit 

che è concettualmente lo stesso per questo insieme di operazioni. La moltiplicazione per base sarà equivalente al turno. Quindi sarei più propenso a usare una routine generale. E disinfettare il codice mentre si disinfettano gli input. E a quel punto, strtoul è probabilmente la soluzione migliore. Ecco un collegamento a a version di strtoul. Quasi tutto il lavoro sta affrontando le condizioni marginali - questo dovrebbe indurvi a capire dove le energie dovrebbero essere focalizzate: codice corretto e resiliente. Il risparmio per l'utilizzo dei bit shift sarà minimo rispetto ai risparmi di say, non andando a crash su input errati.