PRB: реализация HEX atoi - Этюды для программистов

Итак, задача номер два (посложнее

):

Задача:

Написать функцию, которая конвертирует строку (char*), содержащую число в шестнадцатеричном представлении (HEX) в число (int), то есть реализацию atoi для чисел в шестнадцатеричной системе счисления. Прототип функции:

int hex_atoi(const char* hex_string);

Условия:

0. Язык программирования — С/С++.

1. Запрещается пользоваться любыми библиотечными функциями (типа strlen и пр.), а также сторонними классами и иже с ними. В двух словах, задача должна решаться встроенными средствами языка С/С++.

2. Пробельные символы в начале строки (пробел и символ табуляции — \t) опускаются.

3. Знак числа должен сохраняться.

4. Возвращаемое значение — либо 0 в случае ошибки, либо часть числа до момента встречи ошибки (например, если строка содержит значение "0xA0jFD", то возвращаемым значением будет число 160

5. Передаваемая строка содержит числа в шестнадцатеричном формате.

6. Переполнение учитывается (например, вызов hex_atoi("0xFFFFFFFF") выдаст число -1 ).

7. Допускается опускание в строке указания системы счисления (то есть, строки "0xBF" и "BF" идентичны).

8. Запрещается использовать операторы continue и goto в цикле.

9. Количество вспомогательных переменных ограничено тремя.

10. Использование конструкции switch, а также цикла do...while (но не while - его можно) запрещается.

Набор тестов:

hex_atoi("0x3107")         =  12551
hex_atoi(" \t 3107")       =  12551
hex_atoi("0x-3107")        =  0 
hex_atoi("0+x3107")        =  0
hex_atoi("0xa0")           =  160
hex_atoi("0xA1")           =  161
hex_atoi("a0")             =  160
hex_atoi("A1")             =  161
hex_atoi("A0a0t54")        =  41120
hex_atoi("ABCDEF")         =  11259375
hex_atoi("qABCDEF")        =  0 
hex_atoi("0A0")            =  160
hex_atoi("xA0")            =  0
hex_atoi("FFFFFFFF")       = -1
hex_atoi("-FFFFFFFF")      =  1 
hex_atoi("+0x12")          =  18
hex_atoi("-0x12")          = -18
hex_atoi("+a")             =  10
hex_atoi("-a")             = -10
hex_atoi("0")              =  0
hex_atoi(NULL)             =  0

Дерзайте!

07.07.05 14:37: Перенесено из 'Исходники'

За основу взял Ваш код new_atoi

Вот не оптимизированный вариант.
Дальше думаю


int hex_atoi(const char* string)
{
    if(!string) 
        return 0;
    int result = 0;
    
    while(*string == ' ' || *string == '\t')    
        string++;

    bool bNegativeSign = (*string == '-');
    if(bNegativeSign || *string=='+') string++;

    if ((*string == '0') && (*(++string) == 'x'))
        string ++;

    while (*string)
    {
        if (((*string < 48) || (*string > 57)) &&
            ((*string < 'a') || (*string > 'f')) &&
            ((*string < 'A') || (*string > 'F')))
            break;
        result *= 16;
        if ((*string > 48) && (*string < 57))
        {
            result += *string - 48;
        }
        if ((*string >= 'a') && (*string <= 'f'))
            result += *string - 'a' + 10;
        if ((*string >= 'A') && (*string <= 'F'))
            result += *string - 'A' + 10;
        string++;
    }
    return ( bNegativeSign ? -result : result );
}

Если и дальше заняться плагиатом, то из кода глубокоуважаемого oranry
Можно получить следующее

Сам бы во век до такого не додумался

int hex_atoi(char *s)
{
    int sign=1, val=0;
    if (s) while ((*s == ' ' || *s == '\t') && *(++s)); else return 0;
    sign*=(*s == '-' && s++)?-1:((*s == '+' && s++), 1);
    if ((*s == '0') && (*(++s) == 'x')) s++;
    while ((*s>='0' && *s<='9') || (*s>='A' && *s<='F') || (*s>='a' && *s<='f'))
    {
        val*=16;
        if (*s>='0' && *s<='9') val+=*s++ - 48; 
        if (*s>='a' && *s<='f') val+=*s++ - 'a' + 10; 
        if (*s>='A' && *s<='F') val+=*s++ - 'A' + 10; 
    }
    return val*sign;
}

Насчет вариантов 48 + 9 -ну лень калькулятор доставать

int hex_atoi(const char *string)
{
    int sign = 1, value = 0;

    if( string )
    {
        while(*string == ' ' || *string == '\t') string++;
    } 
    else
    {
        return 0;
    }

    if( *string == '+' || *string == '-' )
    {
        sign = (*string == '+') ? 1 : -1;
        string += 1;
    }

    if( *string == '0' && (*(string+1) == 'x' || *(string+1)== 'X') )
    {
        string += 2;
    }

    while( *string )  
    {
        if( *string >= '0' && *string <= '9' )
        {
            value = (value << 4) + (*string - '0');
        }
        else
        if( *string >= 'a' && *string <= 'f')
        {
            value = (value << 4) + (*string - 'a' + 10);
        } 
        else
        if( *string >= 'A' && *string <= 'F' )
        {
            value = (value << 4) + (*string - 'A' + 10);
        } 
        else
        {
            return value * sign;
        }
        string++;
    }

    return value*sign;
}

Здравствуйте Flamer, Вы писали:

F>Итак, задача номер два (посложнее ;) ):

F>Условия:

F>3. Знак числа должен сохраняться.

Гекс со знаком — оу е!

F>4. Возвращаемое значение — либо 0 в случае ошибки, либо часть числа до момента встречи ошибки (например, если строка содержит значение "0xA0jFD", то возвращаемым значением будет число 160

Халява сэр

F>6. Переполнение учитывается (например, вызов hex_atoi("0xFFFFFFFF") выдаст число -1 ).

А "0x123456789" = 0x12345678 или 0x23456789 ?

F>7. Допускается опускание в строке указания системы счисления (то есть, строки "0xBF" и "BF" идентичны).

F>8. Запрещается использовать операторы continue и goto в цикле.
F>10. Использование конструкции switch, а также цикла do...while (но не while - его можно) запрещается.

Любим усложнять жизнь?

int hexatoi(const char* str)
{
  if(!str) return 0;

  int v = 0; // аккумулятор
  bool n = false; // негатив
  char c = *(str++); // пригодится

  // ожидаем пробелы
  while(c == ' ' || c == '\t') c = *(str++);
  if(!c) return 0;

  // ожидаем знак
  // на мой взгляд, так эффективнее, чем громоздить n = (...) ? (...) : (...)
  if(c == '-') { n = true; c = *(str++); }
  else if(c == '+') c = *(str++);
  if(!c) return 0; // В принципе, эту проверку можно опустить. Но она быстрая, облегчит жизнь маломало

  // ожидаем префикс
  // а если это просто 0, то и бог с ним. Не жалко
  if(
    c == '0' &&
    (((c = *(str++)) == 'x') || (c == 'X'))
  ) c = *(str++);

  // ожидаем цифры
  // кто не верит оптимизатору, пусть напишет 55 вместо 'A'-10...
  while(
    (с >= '0' && c <= 'f') && // оптимизирующая проверка - для быстрого отсечения неправильных символов
    ( // повторные проверки c>='0',c<='f' оставлены "для наглядности" (или если убрать оптимизирующую)
      (c >= '0' && c <= '9') && (v <<= 4, v += (c - '0'       ), true) ||
      (c >= 'A' && c <= 'F') && (v <<= 4, v += (c - ('A' - 10)), true) ||
      (c >= 'a' && c <= 'f') && (v <<= 4, v += (c - ('a' - 10)), true)
    )
  ) c = *(str++);

  return n ? -v : v;
}

Здравствуйте Flamer, Вы писали:

F>Итак, задача номер два (посложнее

):

Вопросик можно

А чем она посложнее ? Ну у числа другое основание и все тут.
Для Oct было бы не 16 или 10, а 8. И просто ограничения на символы от 0 до 7.

Здравствуйте Vampire, Вы писали:

V>Здравствуйте Flamer, Вы писали:

F>>Итак, задача номер два (посложнее

):

V>Вопросик можно

А чем она посложнее ? Ну у числа другое основание и все тут.
V>Для Oct было бы не 16 или 10, а 8. И просто ограничения на символы от 0 до 7.
V>

Ну так посложнее же

Пусть немножко, но все-же... Обороты надо набирать постепенно

Здравствуйте Flamer, Вы писали:

F>Здравствуйте Vampire, Вы писали:

V>>Здравствуйте Flamer, Вы писали:

F>>>Итак, задача номер два (посложнее

):

V>>Вопросик можно

А чем она посложнее ? Ну у числа другое основание и все тут.
V>>Для Oct было бы не 16 или 10, а 8. И просто ограничения на символы от 0 до 7.
V>>

F>Ну так посложнее же

Пусть немножко, но все-же... Обороты надо набирать постепенно

Ну тогда вот чисто мат. задачка.
Конвертор чисел по любому основанию.
Это значит не только 2 8 10 16, но и любое другое типа 12 и т.п.

Здравствуйте Vampire, Вы писали:

[skipped]

V>Ну тогда вот чисто мат. задачка.
V>Конвертор чисел по любому основанию.
V>Это значит не только 2 8 10 16, но и любое другое типа 12 и т.п.

Плз, оформите все это в отдельный тред (опишите условия задачи, еще что-то, в общем, поподробнее) — думаю, будет интересно...

Здравствуйте Flamer, Вы писали:

F>Итак, задача номер два (посложнее

):

F>Задача:

F>Написать функцию, которая конвертирует строку (char*), содержащую число в шестнадцатеричном представлении (HEX) в число (int), то есть реализацию atoi для чисел в шестнадцатеричной системе счисления. Прототип функции:
F>Условия:
F>0. Язык программирования — С/С++.
F>1. Запрещается пользоваться любыми библиотечными функциями (типа strlen и пр.), а также сторонними классами и иже с ними. В двух словах, задача должна решаться встроенными средствами языка С/С++.
F>2. Пробельные символы в начале строки (пробел и символ табуляции — \t) опускаются.
F>3. Знак числа должен сохраняться.
F>4. Возвращаемое значение — либо 0 в случае ошибки, либо часть числа до момента встречи ошибки (например, если строка содержит значение "0xA0jFD", то возвращаемым значением будет число 160
F>5. Передаваемая строка содержит числа в шестнадцатеричном формате.
F>6. Переполнение учитывается (например, вызов hex_atoi("0xFFFFFFFF") выдаст число -1 ).
F>7. Допускается опускание в строке указания системы счисления (то есть, строки "0xBF" и "BF" идентичны).
F>8. Запрещается использовать операторы continue и goto в цикле.
F>9. Количество вспомогательных переменных ограничено тремя.
F>10. Использование конструкции switch, а также цикла do...while (но не while - его можно) запрещается.

почему бы не написать сразу универсальную функцию определяюшюю тип числа по началу записи
0x — HEX
0 — OCT
остальное DEC
соответственно проверяя коректность символов (т.е 0xa => 10, а 0a => 0, a => 0)
условия оставим теже, но немного довавим
1. сделать две функции
а. signed long sig_uni_atoi(const char *str);
учитывеет знак, знаковый бит. при переролнении возврашает 0, (т.е 2147483648 => 0)
б. unsigned long usig_uni_atoi(const char *str);
не учитывеет знак, знаковый бит.
(можно дополнить/исправить)

Здравствуйте Vampire, Вы писали:

V>

V>        if (*s>='0' && *s<='9') val+=*s++ - 48; 
V>        if (*s>='a' && *s<='f') val+=*s++ - 'a' + 10; 
V>        if (*s>='A' && *s<='F') val+=*s++ - 'A' + 10; 
V>

Извращаться, так до конца

  (val+=*s + (*s>='0' && *s<='9')?-48:((*s>='a' && *s<='f')?10 - 'a':((*s>='A' && *s<='F')?(10 - 'A')))),++s;

Не проверял, мог и напутать где-нить, со скобками например

Хотя с if-ами нагляднее конечно, только поставьте else, ибо условия взаимоисключающие, а оптимизациям компилера тут как-то не верят

Здравствуйте, Кодт, Вы писали:

[]

Блин, только что проснулся, т.к. как раз понадобилась такая весчь для одной маленькой библиотечки, где, по условию задачи, 30 Кб CRT-runtime тащить низзя... Долго вкуривал в выделенные жирным строчки... И пришел к выводу — браво, маэстро!

К>

[]

К>    ( // повторные проверки c>='0',c<='f' оставлены "для наглядности" 
        // (или если убрать оптимизирующую)
К>      (c >= '0' && c <= '9') && (v <<= 4, v += (c - '0'       ), true) ||
К>      (c >= 'A' && c <= 'F') && (v <<= 4, v += (c - ('A' - 10)), true) ||
К>      (c >= 'a' && c <= 'f') && (v <<= 4, v += (c - ('a' - 10)), true)
К>    )
К>  ) c = *(str++);

К>  return n ? -v : v;
К>}
К>

Здравствуйте, orangy, Вы писали:

[]
O>Извращаться, так до конца

O>  (val+=*s + (*s>='0' && *s<='9')?-48:((*s>='a' && *s<='f')?10 - 'a':((*s>='A' && *s<='F')?(10 - 'A')))),++s; 
O>

Я давно подозревал, что мсье любитель извращенных отношений

Классно.

Здравствуйте, Flamer, Вы писали:

F>Здравствуйте, Кодт, Вы писали:

F>[]

F>Блин, только что проснулся, т.к. как раз понадобилась такая весчь для одной маленькой библиотечки, где, по условию задачи, 30 Кб CRT-runtime тащить низзя... Долго вкуривал в выделенные жирным строчки... И пришел к выводу — браво, маэстро!

в порядке личного бреда:

#include <stdio.h>

int hex_atoi(const char* str)
{
  if(!str)return 0;
  static int cvt[]={0,1,2,3,4,5,6,7,8,9,-1,-1,-1,-1,-1,-1,-1,10,11,12,13,14,15,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,10,11,12,13,14,15};
  int  res=0;
  bool negative=false;
  while(*str==' ' || *str=='\t')str++;
  while(*str=='-' || *str=='+')if(*str++=='-')negative=!negative;
  if(str[0]=='0' && (str[1]=='x' || str[1]=='X'))str+=2;
  while(*str)
  {
    if(*str<'0' || *str>'f')break;
    if(cvt[*str-'0']==-1)break;
    res=(res<<4)|cvt[*str-'0'];
    str++;
  }
  return negative?-res:res;
}

#define CHECK(expr,val) \
  if((expr)!=(val))printf("failed " #expr "(%d)!=" #val "\n",(expr));else printf("ok " #expr "\n")

int main(int argc,char* argv[])
{
CHECK(hex_atoi("0x3107")         ,  12551);
CHECK(hex_atoi(" \t 3107")       ,  12551);
CHECK(hex_atoi("0x-3107")        ,  0);
CHECK(hex_atoi("0+x3107")        ,  0);
CHECK(hex_atoi("0xa0")           ,  160);
CHECK(hex_atoi("0xA1")           ,  161);
CHECK(hex_atoi("a0")             ,  160);
CHECK(hex_atoi("A1")             ,  161);
CHECK(hex_atoi("A0a0t54")        ,  41120);
CHECK(hex_atoi("ABCDEF")         ,  11259375);
CHECK(hex_atoi("qABCDEF")        ,  0);
CHECK(hex_atoi("0A0")            ,  160);
CHECK(hex_atoi("xA0")            ,  0);
CHECK(hex_atoi("FFFFFFFF")       , -1);
CHECK(hex_atoi("-FFFFFFFF")      ,  1);
CHECK(hex_atoi("+0x12")          ,  18);
CHECK(hex_atoi("-0x12")          , -18);
CHECK(hex_atoi("+a")             ,  10);
CHECK(hex_atoi("-a")             , -10);
CHECK(hex_atoi("0")              ,  0);
CHECK(hex_atoi(NULL)             ,  0);
  return 0;
}

Здравствуйте, Flamer, Вы писали:

F>Блин, только что проснулся, т.к. как раз понадобилась такая весчь для одной маленькой библиотечки, где, по условию задачи, 30 Кб CRT-runtime тащить низзя... Долго вкуривал в выделенные жирным строчки... И пришел к выводу — браво, маэстро!

Год спал, ещё год курил?

Ты ж сам задачу поставил, в августе 2002...

... << RSDN@Home 1.1.2 stable >>

Здравствуйте, Flamer, Вы писали:

F>Дерзайте!

а почему нет реализации для __int64 ?

Здравствуйте, Flamer, Вы писали:

F>Итак, задача номер два (посложнее

):
Работать было влом, дело было днём

int hex_atoi(const char* hex_string)
{
    int res = 0;
    int negative = 0;

    if (hex_string)
    {
        while (*hex_string == ' ' || *hex_string == '\t')
            hex_string++;

        if (*hex_string == '-' || *hex_string == '+')
        {
            negative = *hex_string == '-' ? 1 : 0;
            hex_string++;
        }
    
        if (*hex_string == '0' && (*(hex_string + 1) == 'x' || *(hex_string + 1) == 'X'))
            hex_string += 2;
        
        while (*hex_string)
        {
            res <<= 4;
            if (*hex_string >= '0' && *hex_string <= '9')
                res |= *hex_string - '0';
            else if (*hex_string >= 'A' && *hex_string <= 'F')
                res |= *hex_string - 'A' + 10;
            else if (*hex_string >= 'a' && *hex_string <= 'f')
                res |= *hex_string - 'a' + 10;
            else
            {
                res >>= 4;
                hex_string = "";
            }
            
            hex_string++;
        }
    }
    
    return (negative == 1) ? -res : +res;
}

P.S. Я так догадался, return в цикле тоже нельзя использовать. На всякий случай обощолся без него.

Chez, ICQ#161095094

Posted via:RSDN@Home;version:1.1.3;muzikstamp:silent

Chez wrote:

А чем strtol не устраивает?

--
Maxim Yegorushkin

Posted via RSDN NNTP Server 1.9

Здравствуйте, MaximE, Вы писали:

ME>Chez wrote:

ME>А чем strtol не устраивает?
Это не то

1) если префикса 0x нет — рассматривает число как десятичное

5. Передаваемая строка содержит числа в шестнадцатеричном формате.

2) возвращает другие результаты в случае ошибок, а надо:

4. Возвращаемое значение — либо 0 в случае ошибки, либо часть числа до момента встречи ошибки (например, если строка содержит значение "0xA0jFD", то возвращаемым значением будет число 160

3) но самое главное, что задание было поставлено просто как разминка для мозгов !

1. Запрещается пользоваться любыми библиотечными функциями (типа strlen и пр.), а также сторонними классами и иже с ними. В двух словах, задача должна решаться встроенными средствами языка С/С++.
...
8. Запрещается использовать операторы continue и goto в цикле.
9. Количество вспомогательных переменных ограничено тремя.
10. Использование конструкции switch, а также цикла do...while (но не while — его можно) запрещается.

Chez, ICQ#161095094

Posted via:RSDN@Home;version:1.1.3;muzikstamp:silent

От:	Flamer	http://users.livejournal.com/_flamer_/
Дата:	29.08.02 07:47
Оценка:

	От:	Vampire
	Дата:	29.08.02 08:41
	Оценка:

	От:	Vampire
	Дата:	29.08.02 09:14
	Оценка:

	От:	Анатолий
	Дата:	29.08.02 09:29
	Оценка:

	От:	Кодт
	Дата:	29.08.02 09:37
	Оценка:	19 (2)

От:	orangy	http://twitter.com/orangy
Дата:	29.08.02 14:08
Оценка:	22 (2)

От:	Lepsik	figvam.ca
Дата:	24.11.04 18:26
Оценка:

	От:	e-Xecutor
	Дата:	15.04.04 08:54
	Оценка:

	От:	MaximE
	Дата:	06.07.05 15:54
	Оценка: