Conversione efficiente tra esadecimale, binario e decimale in C / C ++

Ho 3 rappresentazioni di base per numeri interi positivi:

  1. Decimale, in variabile lunga senza segno (ad es. Unsigned long int NumDec = 200 ).
  2. Esadecimale, in variabile stringa (ad es. Stringa NumHex = “C8” )
  3. Binario, in 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. Vale a dire 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 efficienza temporale: il minor tempo di esecuzione.

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 è ansible battere le funzioni della libreria.

Quindi, prima misura, e se le prestazioni di queste conversioni sono davvero un problema, allora:

1) In alcune applicazioni / domini alcuni numeri appaiono molto spesso, ad esempio zero, 100, 200, 19.95, può essere così comune che ha senso ottimizzare le tue 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.

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

Molti hanno detto, vale la pena ripeterlo più volte: non ottimizzare queste conversioni finché non hai la prova che sono 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 🙁

Suggerirei semplicemente di usare sprintf e sscanf .

Inoltre, se sei interessato a come è implementato, puoi dare un’occhiata al codice sorgente di glibc, GNU C Library .

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 usando “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 su un 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 i 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.

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

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

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

La risposta breve è per la conversione da long int alle tue stringhe usa 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 nel tuo long int devi solo cercare la stringa corretta e concatenarli.

Per convertire da stringhe a lunghe, puoi semplicemente 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 sumndo i risultati.

EDIT: puoi anche 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.

Pensiamo all’incirca alla metà del compito per un momento: convertendo da una base ad arco stringa n a unsigned long, dove n è una potenza di 2 (base 2 per binario e base 16 per hex).

Se il tuo input è sano, allora 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 supponiamo che il tuo contributo 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) 

Lo vedi quanto è facile? 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 cambi. È 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. Ottieni

 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 link a una versione 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.

Perché non usare 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 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 );