Эффективно конвертировать между Hex, Binary и Decimal в C/C++

Question

У меня 3 базовые представления для положительных целых чисел:

1. Десятичный, в беззнаковое длинной переменной (например, без знака длиной INT NumDec = 200).
2. Hex, в строковой переменной (например, строка NumHex = "С8")
3. Binary, в строке переменной (например, строка NumBin = "11001000")

Я хочу, чтобы иметь возможность конвертировать между числами во всех трех представлениях наиболее эффективным способом. То есть для реализации следующих 6 функций:

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

Каков наиболее эффективный подход для каждого из них? Я могу использовать C и C++, но не увеличивать.

Редактировать: «Эффективность» Я имею в виду эффективность времени: кратчайшее время выполнения.

Answer 1

Как уже указывали другие, я бы начал с sscanf(), printf() и/или strtoul(). Они достаточно быстры для большинства приложений, и у них меньше шансов получить ошибки. Я скажу, однако, что эти функции более общие, чем вы могли ожидать, поскольку они должны иметь дело с наборами символов, отличными от ASCII, с числами, представленными в любой базе и так далее. Для некоторых доменов можно бить библиотечные функции.

Таким образом, измерение первой, и если производительность этих конвертации действительно вопрос, то:

1) В некоторых приложениях/доменов определенные числа появляются очень часто, например, ноль, 100, 200, 19.95, может быть настолько распространенным, что имеет смысл оптимизировать ваши функции для преобразования таких чисел с помощью набора операторов if(), а затем вернуться к общим библиотечным функциям. 2) Используйте поиск таблицы, если наиболее распространенные 100 номеров, а затем снова возвращайтесь к библиотечной функции. Помните, что большие таблицы могут не вписываться в ваш кеш и могут потребовать множественные указания для разделяемых библиотек, поэтому тщательно измерьте эти вещи, чтобы убедиться, что вы не снижаете производительность.

Вы также можете посмотреть функции повышения lexical_cast, хотя по моему опыту последние сравниваются с хорошими старыми функциями C.

Жесткие многие говорили об этом, стоит повторять снова и снова: не оптимизируйте эти преобразования, пока не получите доказательства того, что они являются проблемой. Если вы оптимизируете, измерьте свою новую реализацию, чтобы убедиться, что она быстрее и убедитесь, что у вас есть тонна модульных тестов для вашей собственной версии, потому что вы вводите ошибки :-(

Answer 2

Это зависит от того, для чего вы оптимизируете, что вы подразумеваете под «эффективным»? Важно ли, чтобы преобразования были быстрыми, использовали небольшую память, мало времени программиста, меньше WTFs от других программистов, читающих код, или что?

Для удобства чтения и простоты реализации вы должны как минимум реализовать как Dec2Hex(), так и Dec2Binary(), просто позвонив strotul(). Это делает их однострочными, что очень эффективно, по крайней мере, для некоторых из приведенных выше толкований слова.

Answer 3

Звучит очень похоже на проблемы в выполнении домашних заданий, но какого черта ...

Короткий ответ для преобразования из длинных междунар в ваши строки использовать две таблицы поиска. Каждая таблица должна содержать 256 записей. Один сопоставляет байты с шестнадцатеричной строкой: 0 -> «00», 1 -> «01» и т. Д. Другой отображает байт в битовую строку: 0 -> «00000000», 1 -> «00000001».

Затем для каждого байта в вашем длинном int вам просто нужно найти правильную строку и объединить ее.

Чтобы преобразовать из строк обратно в длинный, вы можете просто преобразовать шестнадцатеричную строку и битовую строку обратно в десятичное число, умножив числовое значение каждого символа на соответствующую мощность 16 или 2 и суммируя результаты.

EDIT: вы также можете использовать те же таблицы поиска для обратного преобразования, выполнив двоичный поиск, чтобы найти нужную строку. Для этого потребуется log (256) = 8 сравнений ваших строк. К сожалению, у меня нет времени для анализа, будет ли сравнение строк намного быстрее, чем умножение и добавление целых чисел.

Answer 4

Я бы предложил только использовать sprintf и sscanf.

Также, если вас интересует, как это реализовано, вы можете взглянуть на source code на номер glibc, the GNU C Library.

Answer 5

Почему бы просто не использовать макрос, чтобы также принять формат ввода. Если вы хотя бы на 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); 

Или вы можете использовать sprintf напрямую: или у вас может быть несколько макросов.

#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

Почему эти процедуры должны быть такими эффективными по времени? Такое требование всегда заставляет меня задуматься. Вы уверены, что очевидные методы преобразования, такие как strtol(), слишком медленные или что вы можете сделать лучше? Системные функции обычно довольно эффективны. Они иногда медленнее поддерживают общность и проверку ошибок, но вам нужно учитывать, что делать с ошибками. Если аргумент bin имеет символы, отличные от '0' и '1', что тогда? Прервать? Пропагандировать массовые ошибки?

Почему вы используете «Дек» для представления внутреннего представления? Dec, Hex и Bin следует использовать для обозначения строковых представлений. Нет ничего десятичного о unsigned long. Вы имеете дело со строками, показывающими число в десятичном значении? Если нет, вы сбиваете с толку людей и собираетесь запутать еще много.

Преобразование между двоичными и шестнадцатеричными текстовыми форматами может быть выполнено быстро и эффективно с помощью таблиц поиска, но все, что связано с десятичным текстовым форматом, будет более сложным.

Answer 7

Давайте рассмотрим половину задачи на мгновение - преобразование из строковой базы n в unsigned long, где n - мощность 2 (база 2 для двоичного и базового 16 для шестнадцатеричного).

Если ваш ввод является нормальным, то эта работа представляет собой не что иное, как сравнение, подобие, сдвиг и цифру. Если ваш вход не нормальный, ну, вот где он становится уродливым, не так ли? Выполнение преобразования сверхбыстрого не сложно. Сделать это хорошо при любых обстоятельствах - задача.

Итак, давайте предположим, что ваш вклад в здравом уме, то сердце вашего преобразования заключается в следующем:

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) 

Посмотрите, как легко это? И это приведет к сбою в нестандартных входах. Большая часть вашей работы будет идти навстречу твоему входу, а не производительности.

Теперь этот код использует преимущества двух сдвигов. Легко распространяться на основание 4, основание 8, основание 32 и т. Д. Он не будет работать на немодулях двух оснований. Для них ваша математика должна измениться. Вы получаете

val = (val * base) + digit 

, что концептуально одинаково для этого набора операций. Умножение на базу будет эквивалентно сдвигу. Поэтому я скорее всего воспользуюсь полностью обычной рутиной. И санируйте код при дезинфекции входов. И в этот момент, strtoul, вероятно, ваш лучший выбор. Вот ссылка на a version strtoul. Почти вся работа связана с крайними условиями - это должно указывать на то, где вы должны сосредоточиться: правильный, устойчивый код. Экономия на использовании бит-сдвигов будет минимальной по сравнению с экономией, скажем, без сбоев при плохом вводе.