Converter de forma eficiente entre Hex, binário, e decimal em C / C ++

StackOverflow https://stackoverflow.com/questions/819487

  •  03-07-2019
  •  | 
  •  

Pergunta

Eu tenho 3 representações de base para números inteiros positivos:

  1. decimal, em variável longa sem assinatura (por exemplo, longo unsigned int NumDec = 200 ).
  2. Hex, em cadeia variável (por exemplo, string NumHex = "C8" )
  3. Binário, na cadeia variável (por exemplo, string NumBin = "11001000" )

Eu quero ser capaz de converter entre os números em todos os 3 representações da forma mais eficiente. Ou seja, para implementar as 6 funções seguintes: 

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

O que é a abordagem mais eficiente para cada um deles? Eu posso usar C e C ++, mas não aumentar.

Edit: por "eficiência" Quero dizer a eficiência de tempo:. Tempo de execução mais curto

Foi útil?

Solução

Como os outros têm para fora pontas, eu começaria com sscanf() , printf() e / ou strtoul() . Eles são rápidos o suficiente para a maioria das aplicações, e eles são menos propensos a ter bugs. Posso dizer, no entanto, que estas funções são mais genéricas do que você poderia esperar, como eles têm de lidar com conjuntos de caracteres não-ASCII, com números representados em qualquer base e assim por diante. Para alguns domínios é possível vencer as funções da biblioteca.

Assim, medir primeiro lugar, e se o desempenho destes conversão é realmente um problema, então:

1) Em algumas aplicações / domínios certos números aparecem com muita frequência, por exemplo zero, 100, 200, 19,95, pode ser tão comum que faz sentido para otimizar suas funções para converter tais números com um monte de if () declarações e, em seguida, cair de volta para as funções de biblioteca genéricos. 2) Use uma consulta à tabela se os 100 números mais comuns, e depois voltar a cair uma função de biblioteca. Lembre-se que grandes tabelas podem não caber no seu cache e pode exigir múltiplas indireções para bibliotecas compartilhadas, para medir essas coisas com cuidado para se certificar de que você não está diminuindo o desempenho.

Você também pode querer olhar para boost lexical_cast funções, embora na minha experiência os últimos são relativamente em comparação com as boas funções C antigos.

muitas resistente ter dito isso, vale a pena repetir uma e outra vez: não otimizar essas conversões até que você tenha provas de que eles são um problema. Se você fizer otimizar, medir a sua nova aplicação para se certificar de que é mais rápido e verifique se você tem uma tonelada de testes de unidade para a sua própria versão, porque você vai introduzir erros: - (

Outras dicas

Gostaria de sugerir apenas usando sprintf e sscanf .

Além disso, se você estiver interessado em como ele é implementado você pode dar uma olhada na código fonte para glibc, o GNU C Library .

Por que essas rotinas tem que ser tão eficiente tempo? Esse tipo de alegação sempre me faz pensar. Tem a certeza que os métodos de conversão óbvias como strtol () são muito lentos, ou que você pode fazer melhor? As funções do sistema são geralmente muito eficiente. Eles são, por vezes, mais lenta a generalidade apoio e verificação de erros, mas você precisa considerar o que fazer com os erros. Se um argumento bin tem outros que '0' e '1' caracteres, o que então? Abortar? Propagar erros enormes?

Por que você está usando "Dezembro" para representar a representação interna? Dez Hex, e Bin deve ser usado para se referir às representações de seqüência. Não há nada decimal cerca de uma unsigned long. Você está lidando com cordas que mostram o número em decimal? Se não, você está confundindo as pessoas aqui e está indo para confundir muitos mais.

A transformação entre formatos de texto binário e Hex pode ser feito de forma rápida e eficiente, com tabelas de pesquisa, mas qualquer coisa que envolva formato de texto decimal será mais complicado.

Isso depende do que você está otimizando para, o que você quer dizer com "eficiente"? É importante que as conversões de ser rápido, usar pouca memória, pouco tempo programador, menos WTFs de outros programadores a leitura do código , ou o quê?

Para facilitar a leitura e facilidade de implementação, você deve pelo menos implementar tanto Dec2Hex() e Dec2Binary() por apenas chamando strotul(). Isso torna-os em one-liners, que é muito eficiente para, pelo menos, algumas das interpretações acima da palavra.

soa muito como um problema lição de casa, mas o que diabos ...

A resposta curta é para a conversão de long int para suas cordas usar duas tabelas de pesquisa. Cada tabela deve ter 256 entradas. Um mapeia um byte para uma string hex: 0 -> "00", 1 -> "01", etc. Os outros mapas um byte para uma cadeia de bits:. 0 -> "00000000", 1 -> "00000001"

Então, para cada byte em sua longa int você apenas tem que olhar a seqüência correta e concatenar-los.

Para converter de cordas voltar ao tempo você pode simplesmente converter a string hex ea cadeia de volta pouco a um número decimal multiplicando o valor numérico de cada personagem pelo poder apropriado de 16 ou 2, e somando-se os resultados.

EDIT: Você também pode usar as mesmas tabelas de referência para conversão para trás, fazendo pesquisa binária para localizar a cadeia direita. Este registo levaria (256) = 8 comparações de suas cordas. Infelizmente eu não tenho tempo para fazer a análise se comparando strings seria muito mais rápido do que multiplicando e adicionando números inteiros.

Vamos pensar sobre a metade de tarefa por um momento - a conversão de uma base ized cordas n para unsigned long, onde n é uma potência de 2 (base 2 para binário e base 16 para hex)

.

Se a sua entrada é são, então este trabalho não é nada mais do que uma comparação, um subract, uma mudança e um ou por dígito. Se sua entrada não é são, bem, isso é onde fica feio, não é? Fazer o super rápida conversão não é difícil. Fazê-lo bem em todas as circunstâncias é o desafio.

Então, vamos assumir que a sua entrada é são, então o coração de sua conversão é o seguinte: 

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)

Veja como é fácil? E ele irá falhar em entradas não são. A maioria de seu trabalho está indo para ir para tornar a sua sã entrada, não o desempenho.

Agora, este código aproveita potência de dois mudança. É fácil alargar a base 4, a base 8, a base 32, etc, não irá funcionar em não poder de duas bases. Para aqueles, a sua matemática tem que mudar. Você começa 

val = (val * base) + digit

que é conceitualmente o mesmo para este conjunto de operações. A multiplicação pela base vai ser equivalente à mudança. Então eu seria tão propensos a usar uma rotina totalmente geral em seu lugar. E higienizar o código enquanto higienização das entradas. E nesse ponto, strtoul é provavelmente a sua melhor aposta. Aqui está um link para uma versão de strtoul. Quase todo o trabalho está a lidar com condições de borda - que deve você na pista de onde você energias devem ser focados: correta código e resiliente. A poupança para usar deslocamentos bit vai ser mínima em comparação com as economias de digamos, não bater na entrada ruim.

Por que não usar uma macro para também ter o formato como uma entrada. Se você estiver em C, pelo menos. 

#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 você pode usar sprintf diretamente:. Ou você pode ter vários 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 );
Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top