Converti in modo efficiente tra esadecimale, binario e decimale in C / C ++

Question

Ho 3 rappresentazioni di base per numeri interi positivi:

1. Decimale, in variabile lunga senza segno (ad es. int inteso lungo NumDec = 200 ).
2. Esadecimale, nella variabile stringa (ad es. stringa NumHex = " C8 " )
3. Binario, nella variabile stringa (ad es. 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 ciascuno di essi? Posso usare C e C ++, ma non aumentare.

Modifica: per " efficienza " Intendo l'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 possa aspettare, poiché devono gestire set di caratteri non ASCII, con numeri rappresentati in qualsiasi base e così via. Per alcuni domini è possibile battere le funzioni della libreria.

Quindi, misura prima e se il rendimento di queste conversioni è davvero un problema, allora:

1) In alcune applicazioni / domini alcuni numeri appaiono molto spesso, ad esempio zero, 100, 200, 19,95, potrebbe essere così comune che ha senso ottimizzare le funzioni per convertire tali numeri con un mucchio di istruzioni if ??() e quindi tornare alle funzioni di libreria generiche. 2) Utilizzare una ricerca tabella se i 100 numeri più comuni, quindi ricadere su una funzione di libreria. Ricorda che le tabelle di grandi dimensioni potrebbero non adattarsi alla tua cache e potrebbero richiedere più indicazioni indirette per le librerie condivise, quindi misura attentamente queste cose per assicurarti di non ridurre le prestazioni.

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

Molti lo hanno detto, vale la pena ripeterlo ancora e ancora: non ottimizzare queste conversioni fino a quando non avrai la prova che sono un problema. Se ottimizzi, misura la tua nuova implementazione per assicurarti che e siano più veloci e assicurati di avere un sacco di test unitari per la tua versione, perché introducerai dei bug :-(

Answer 2

Suggerirei di usare sprintf e sscanf .

Inoltre, se sei interessato a come viene implementato, puoi dare un'occhiata al codice sorgente per glibc, la libreria GNU C .

Answer 3

Perché queste routine devono essere così efficienti in termini di tempo? Questo tipo di affermazione mi fa sempre meravigliare. Sei sicuro che i metodi di conversione ovvi come strtol () siano troppo lenti o che puoi fare di meglio? Le funzioni di sistema sono generalmente 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 ha caratteri diversi da '0' e '1', e allora? Interrompere? Propagare errori enormi?

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

La trasformazione tra i formati di testo binario ed esadecimale può essere eseguita in modo rapido ed efficiente, con tabelle di ricerca, ma qualsiasi cosa che implichi un formato di testo decimale sarà più complicata.

Answer 4

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

Per leggibilità e facilità di implementazione, dovresti almeno implementare sia Dec2Hex () che Dec2Binary () semplicemente chiamando strotul () . Ciò li rende in una riga, il che è molto efficace per almeno alcune delle interpretazioni della parola sopra menzionate.

Answer 5

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

La risposta breve è per convertire da long int a stringhe usando due tabelle di ricerca. Ogni tabella dovrebbe avere 256 voci. Uno associa un byte a una stringa esadecimale: 0 - > " 00 " ;, 1 - > " 01 " ;, ecc. L'altro mappa un byte su una stringa di bit: 0 - > "00000000", 1 - > & Quot; 00000001 ".

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

Per convertire da stringhe di nuovo in long puoi semplicemente convertire la stringa esadecimale e la stringa di bit in un numero decimale moltiplicando il valore numerico di ciascun carattere per la potenza appropriata di 16 o 2 e sommando i risultati.

EDIT: puoi anche usare le stesse tabelle di ricerca per la conversione all'indietro facendo una ricerca binaria per trovare la stringa giusta. Ciò richiederebbe log (256) = 8 confronti delle stringhe. Sfortunatamente non ho tempo di fare l'analisi se il confronto delle stringhe sarebbe molto più veloce della moltiplicazione e dell'aggiunta di numeri interi.

Answer 6

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

Se il tuo input è sano, allora questo lavoro non è altro che un confronto, un sottoratto, 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. Fare bene in tutte le circostanze è la sfida.

Supponiamo quindi che il tuo input sia sano, quindi il cuore della tua 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)

Vedi quanto è facile? E fallirà su input non sani. Gran parte del tuo lavoro sta andando a rendere sano il tuo input, non le prestazioni.

Ora, questo codice sfrutta la potenza di due turni. È facile estenderlo alla base 4, alla base 8, alla base 32, ecc. Non funzionerà con l'assenza di due basi. Per quelli, la tua matematica deve cambiare. Ottieni

val = (val * base) + digit

che è concettualmente lo stesso per questo insieme di operazioni. La moltiplicazione per la base sarà equivalente allo spostamento. Quindi avrei la stessa probabilità di utilizzare una routine completamente generale. E disinfetta il codice mentre disinfetta gli input. E a quel punto, strtoul è probabilmente la soluzione migliore. Ecco un link a una versione di strtoul. Quasi tutto il lavoro sta gestendo le condizioni al limite - ciò dovrebbe indurti a capire dove concentrare le tue energie: codice corretto e resiliente. I risparmi per l'utilizzo di bit shift saranno minimi rispetto ai risparmi di dire, non si arrestano in modo anomalo in caso di input errato.

Answer 7

Perché non usare semplicemente una Macro per prendere anche il formato come input. Se sei almeno in C.

#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 puoi usare direttamente sprintf: oppure puoi avere più macro.

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