Эффективное преобразование между шестнадцатеричным, двоичным и десятичным кодами в C/C ++

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

  •  03-07-2019
  •  | 
  •  

Вопрос

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

  1. Десятичный, в длинной переменной без знака (например, unsigned long int NumDec = 200).
  2. Шестнадцатеричная, в строковой переменной (например, строка NumHex = "C8")
  3. Двоичный файл, в строковой переменной (например, строка NumBin = "11001000")

Я хочу иметь возможность конвертировать числа во всех 3 представлениях наиболее эффективным способом.То есть.для реализации следующих 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 ++, но не boost.

Редактировать:Под "эффективностью" я подразумеваю временную эффективность:Самое короткое время выполнения.

Это было полезно?

Решение

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

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

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

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

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

Другие советы

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

Кроме того, если вам интересно, как это реализовано, вы можете взглянуть на исходный код для glibc, библиотеки GNU C .

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

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

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

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

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

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

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

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

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

РЕДАКТИРОВАТЬ: Вы также можете использовать те же таблицы поиска для обратного преобразования, выполнив бинарный поиск, чтобы найти правильную строку. Это займет log (256) = 8 сравнений ваших строк. К сожалению, у меня нет времени для анализа, будет ли сравнение строк намного быстрее, чем умножение и добавление целых чисел.

Давайте на мгновение подумаем о половине задачи - преобразовании из строкового базового значения n в беззнаковое 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, вероятно, ваш лучший выбор.Вот ссылка на версия из стратула.Почти вся работа связана с обработкой граничных условий - это должно подсказать вам, на чем следует сосредоточить вашу энергию:правильный, устойчивый код.Экономия при использовании битовых сдвигов будет минимальной по сравнению с экономией, скажем, при отсутствии сбоев при неправильном вводе.

Почему бы просто не использовать макрос, чтобы также принять формат в качестве входных данных. Если вы находитесь в 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 );
Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top