Convertissez efficacement entre Hex, Binary et Decimal en C / C ++

Question

J'ai 3 représentations de base pour les nombres entiers positifs:

1. Décimal, variable longue non signée (par exemple, unsigned long int NumDec = 200 ).
2. Hex, variable de chaîne (par exemple, chaîne NumHex = "C8" )
3. Binaire, dans la variable chaîne (par exemple, chaîne NumBin = "11001000" )

Je veux pouvoir convertir les nombres de toutes les 3 représentations de la manière la plus efficace. C'est à dire. pour implémenter les 6 fonctions suivantes:

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

Quelle est l’approche la plus efficace pour chacun d’entre eux? Je peux utiliser C et C ++, mais pas de boost.

Modifier: Par "efficacité" Je parle d’efficacité: le temps d’exécution le plus court.

Answer 1

Comme d'autres l'ont déjà souligné, je commencerais par sscanf ( ) , printf () et / ou strtoul () . Ils sont assez rapides pour la plupart des applications et sont moins susceptibles d’avoir des bogues. Je dirai cependant que ces fonctions sont plus génériques que ce à quoi on pourrait s’attendre, car elles doivent traiter des jeux de caractères non-ASCII, avec des nombres représentés dans n’importe quelle base, etc. Pour certains domaines, il est possible de battre les fonctions de la bibliothèque.

Alors, mesurez d’abord, et si les performances de ces conversions posent vraiment problème, alors:

1) Dans certaines applications / domaines, certains nombres apparaissent très souvent, par exemple zéro, 100, 200, 19.95, cela peut être si courant qu'il est logique d'optimiser vos fonctions pour convertir ces nombres avec un tas d'instructions if () , puis retomber sur les fonctions de la bibliothèque générique. 2) Utilisez une table pour rechercher les 100 numéros les plus courants, puis utilisez une fonction de bibliothèque. N'oubliez pas que les grandes tables peuvent ne pas tenir dans votre cache et peuvent nécessiter plusieurs indirections pour les bibliothèques partagées; mesurez donc ces éléments avec soin pour vous assurer de ne pas réduire les performances.

Vous voudrez peut-être aussi examiner les fonctions boost lexical_cast, bien que, selon mon expérience, ces dernières soient relativement comparées aux bonnes vieilles fonctions C.

Bien que beaucoup l’aient dit, il est bon de le répéter encore et encore: n’optimisez pas ces conversions tant que vous n’avez pas la preuve qu’elles posent problème. Si vous optimisez, mesurez votre nouvelle implémentation pour vous assurer qu'elle est plus rapide et et assurez-vous de disposer d'une tonne de tests unitaires pour votre propre version, car vous introduirez des bogues: - (

Answer 2

Je suggérerais simplement d’utiliser sprintf et sscanf .

De plus, si vous êtes intéressé par la façon dont il est mis en œuvre, vous pouvez consulter le code source. pour la glibc, la bibliothèque GNU C .

Answer 3

Pourquoi ces routines doivent-elles être si rapides? Ce genre de revendication me laisse toujours perplexe. Êtes-vous sûr que les méthodes de conversion évidentes telles que strtol () sont trop lentes ou que vous pouvez faire mieux? Les fonctions du système sont généralement assez efficaces. La prise en charge de la généralité et de la vérification des erreurs est parfois plus lente, mais vous devez décider quoi faire des erreurs. Si un argument bin a des caractères autres que "0" et "1", alors quoi? Avorter? Propager des erreurs massives?

Pourquoi utilisez-vous " Dec " représenter la représentation interne? Dec, Hex et Bin doivent être utilisés pour faire référence aux représentations de chaîne. Il n'y a rien de décimal à propos d'un unsigned long . Avez-vous affaire à des chaînes indiquant le nombre en décimal? Sinon, vous confondez les gens ici et vous allez en confondre beaucoup plus.

La transformation entre les formats de texte binaire et hexadécimal peut être effectuée rapidement et efficacement à l'aide de tables de recherche, mais tout ce qui concerne le format de texte décimal sera plus compliqué.

Answer 4

Cela dépend de ce que vous optimisez, qu'entendez-vous par "efficace"? Est-il important que les conversions soient rapides, utilisent peu de mémoire, peu de temps de programmation, moins de WTF des autres programmeurs lisant le code ou quoi?

Pour des raisons de lisibilité et de facilité de mise en œuvre, vous devez au moins implémenter les codes Dec2Hex () et Dec2Binary () en appelant simplement strotul () . Cela les rend uniques, ce qui est très efficace pour au moins certaines des interprétations précédentes du mot.

Answer 5

Cela ressemble beaucoup à un problème de devoirs, mais bon sang…

La réponse courte est de convertir deux tables de correspondance pour convertir de long int en chaînes. Chaque table devrait avoir 256 entrées. On mappe un octet à une chaîne hexagonale: 0 - > "00", 1 - > "01", etc. L’autre mappe un octet sur une chaîne de bits: 0 - > & amp; 00000000 " ;, 1 - > "00000001".

Ensuite, pour chaque octet de votre long int, il vous suffit de rechercher la chaîne correcte et de les concaténer.

Pour convertir des chaînes longues en chaînes longues, vous pouvez simplement convertir la chaîne hexadécimale et la chaîne de bits en un nombre décimal en multipliant la valeur numérique de chaque caractère par la puissance appropriée de 16 ou 2 et en faisant la somme des résultats.

EDIT: Vous pouvez également utiliser les mêmes tables de recherche pour la conversion en arrière en effectuant une recherche binaire pour trouver la bonne chaîne. Cela prendrait log (256) = 8 comparaisons de vos chaînes. Malheureusement, je n'ai pas le temps d'analyser si la comparaison de chaînes serait beaucoup plus rapide que la multiplication et l'ajout d'entiers.

Answer 6

Réfléchissons un instant à la moitié de la tâche - convertir une base n chaîne en chaînes non signées en longueur, où n est une puissance de 2 (base 2 pour binaire et base 16 pour hex).

Si votre saisie est saine, ce travail n’est rien d’autre qu’une comparaison, une sous-activité, un décalage et un chiffre ou. Si votre contribution n'est pas saine d'esprit, eh bien, c'est là que ça devient laide, n'est-ce pas? Faire la conversion ultra-rapide n'est pas difficile. Le défi est de le bien faire en toutes circonstances.

Supposons donc que votre entrée est saine, alors le cœur de votre conversion est le suivant:

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)

Vous voyez comme c'est facile? Et cela échouera sur les entrées non sensées. La majeure partie de votre travail va rendre votre entrée saine, et non votre performance.

Maintenant, ce code tire parti de la puissance de deux transferts. Il est facile de s'étendre aux bases 4, 8, 32, etc. Cela ne fonctionnera pas si deux bases ne sont pas alimentées. Pour ceux-là, vos calculs doivent changer. Vous obtenez

val = (val * base) + digit

qui est conceptuellement le même pour cet ensemble d'opérations. La multiplication par la base va être équivalente au décalage. Donc, je serais tout aussi susceptible d'utiliser une routine entièrement générale à la place. Et désinfectez le code tout en désinfectant les entrées. Et à ce stade, strtoul est probablement votre meilleur choix. Voici un lien vers une version

Answer 7

Pourquoi ne pas simplement utiliser une macro pour prendre également le format en entrée. Si vous êtes en C au moins.

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

Ou vous pouvez utiliser directement sprintf: Ou vous pouvez avoir plusieurs macros.

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