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

Question

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

1. Десятичное число в переменной без знака long (например, long без знака int NumDec = 200 ).
2. Hex, в строковой переменной (например, string NumHex = "C8" )
3. Двоичный, в строковой переменной (например, string 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 ++, но не Boost.

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

Answer 1

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

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

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

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

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

Answer 2

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

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

Answer 3

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

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

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

Answer 4

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

Для удобочитаемости и простоты реализации вы должны по крайней мере реализовать Dec2Hex() и Dec2Binary(), просто вызвав <a href="http://www.manpagez.com/man/3/strtoul/" rel="nofollow noreferrer">strotul()</a>. Это делает их однострочными, что очень эффективно по крайней мере для некоторых из приведенных выше толкований слова.

Answer 5

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

Answer 6

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

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

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

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

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

Answer 7

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