Здравствуйте, Tirael, Вы писали:
T>В общемто сабж, а да к исходникам не отылать смотрел ни хера не понял да и еще там тоже стандартные библы юзаються
ну можно в принципе перебирать каждый символ, проверять его какое нить ASCII-код и формировать число. Только такое решение не очень будет переносимым имхо. А если для винды то в ней есть функции которые проверяют является ли char цифрой, что то вроде IsAlphaNum но точно не помню
Здравствуйте, Tirael, Вы писали:
T>В общемто сабж, а да к исходникам не отылать смотрел ни хера не понял да и еще там тоже стандартные библы юзаються
int atoi(const char *s)
{
int i = 0;
while (*s && *s >= '0' && *s <= '9')
{
i *= 10;
i += *s++ — '0';
}
return i;
}
естественно невалидные символы можно обрабатывть по-другому.
Кроме того нужно добавить проверку на переполнение +
проверку на то что первый символ может быть минусом.
А да, еще можно скипать пробелы впереди.
Но основная идея я надеюсь понятна.
Re: Как Реализовать atoi без стандартных библиотек
Здравствуйте, Tirael, Вы писали:
T>В общемто сабж, а да к исходникам не отылать смотрел ни [****] не понял да и еще там тоже стандартные библы юзаються
Нарожал...
Спать пора, а я [*****] занимаюсь
Вот как imho должна выглядить библиотека вывода, которая не привязывает пользователя к iostream. Куда хотим, туда и печатаем, хоть в char*, хоть в std::vector, хоть в поток.
Кстати, в 5 раз быстрее стандартного atoi, если печать в массив.
//(c)_Winnie.namespace detail
{
template <class CharT>
inline char DigitToChar(int i) { return CharT('0'+i); }
template <class CharT>
inline CharT Minus() { return'-'; }
template <class CharT>
inline CharT Plus() { return'+'; }
template <class CharT>
inline CharT Space() { return' '; }
inline int DivideBy10(int n)
{
struct sizeof_int_4 { int assert[sizeof(int) == 4 ? 1 : -1]; };
const int magic32 = -858993459;
return (magic32*n) >> 1; //division by 10;
}
}
enum PrintPlus
{
PrintPlusAsBlank=0,
PrintPlusAsPlus=1,
PrintPlusAsSpace=2
};
template <class OutIter>
OutIter Print(int i, OutIter out, PrintPlus print_plus= PrintPlusAsBlank)
{
typedef char CharT;
bool print_zero = false; //do not print leading zeroes. do print internal zeroes;struct sizeof_int_4 { int assert[sizeof(int) == 4 ? 1 : -1]; };
int n = 1000000000;
if (i < 0)
{
*out++ = detail::Minus<CharT>();
i= -i;
}
else
{
if (print_plus)
{
*out= print_plus == PrintPlusAsPlus ? detail::Plus<CharT>() : detail::Space<CharT>();
}
}
if (i == 0x80000000)
{
int ix80000000[10]= {2,1,4,7,4,8,3,6,4,8};
for(int digit_num=0; digit_num<10; ++digit_num)
*out++= detail::DigitToChar<CharT>(ix80000000[digit_num]);
return out;
}
{
int nn= n;
int digit= 0; //digit is in [0..9] rangewhile (i >= nn && nn>0) //"nn+= n" may cause overflow
{
++digit;
nn+= n;
}
if (digit)
print_zero= true;
nn-= n;
if (print_zero)
*out++ = detail::DigitToChar<CharT>(digit);
i-= nn;
n= detail::DivideBy10(n);
}
for(int digit_num=0; digit_num<8; ++digit_num)
{
int nn= n;
int digit= 0; //digit is in [0..9] rangewhile (i >= nn)
{
++digit;
nn+= n;
}
if (digit)
print_zero= true;
nn-= n;
if (print_zero)
*out++ = detail::DigitToChar<CharT>(digit);
i-= nn;
n= detail::DivideBy10(n);
}
{
int nn= n;
int digit= 0; //digit is in [0..9] rangewhile (i >= nn)
{
++digit;
nn+= n;
}
*out++ = detail::DigitToChar<CharT>(digit);
}
return out;
}
Здравствуйте, Tirael, Вы писали:
T>В общемто сабж, а да к исходникам не отылать смотрел ничего не понял да и еще там тоже стандартные библы юзаються
Далеко ходить не нужно, можно, например, реализацию у WTL позаимствовать:
atlmisc.h
static int _cstrtoi(const TCHAR* nptr)
{
int c; /* current char */int total; /* current total */int sign; /* if '-', then negative, otherwise positive */while ( _cstrisspace(*nptr) )
++nptr;
c = (int)(_TUCHAR)*nptr++;
sign = c; /* save sign indication */if (c == _T('-') || c == _T('+'))
c = (int)(_TUCHAR)*nptr++; /* skip sign */
total = 0;
while (_cstrisdigit((TCHAR)c)) {
total = 10 * total + (c - '0'); /* accumulate digit */
c = (int)(_TUCHAR)*nptr++; /* get next char */
}
if (sign == '-')
return -total;
else
return total; /* return result, negated if necessary */
}
Ф-ции _cstrisdigit и _cstrisspace будут работать только под Win, поэтому для Win-независимости придется написать свои аналоги.
static int _cstrisdigit(TCHAR ch)
{
WORD type;
GetStringTypeEx(GetThreadLocale(), CT_CTYPE1, &ch, 1, &type);
return (type & C1_DIGIT) == C1_DIGIT;
}
static int _cstrisspace(TCHAR ch)
{
WORD type;
GetStringTypeEx(GetThreadLocale(), CT_CTYPE1, &ch, 1, &type);
return (type & C1_SPACE) == C1_SPACE;
}
Re[3]: Как Реализовать atoi без стандартных библиотек
On Wed, 03 Nov 2004 08:56:11 GMT, alnsn <21403@news.rsdn.ru> wrote:
> ME>А зачем этот трюк с умножением на magic32 и последующим сдвигом? Это намного быстрее простого деления? > > Наверно ему очень книга www.hackersdelight.org понравилась
Я хочу узнать действительно ли умножение быстрее деления? Если бы это было сложение и сдвиг, то да, но вот умножение вместо деления...
-- Maxim Yegorushkin
Posted via RSDN NNTP Server 1.9 gamma
Re[5]: Как Реализовать atoi без стандартных библиотек
Здравствуйте, MaximE, Вы писали:
ME>Я хочу узнать действительно ли умножение быстрее деления? Если бы это было сложение и сдвиг, то да, но вот умножение вместо деления...
для float однозначно быстрее, для int скорее всего быстрее
при умножении не может быть вызвано прерывание "деление на ноль", что уже говорит о том, что операция проще.
... << RSDN@Home 1.1.3 stable >>
Re[5]: Как Реализовать atoi без стандартных библиотек
Здравствуйте, MaximE, Вы писали:
ME>On Wed, 03 Nov 2004 08:56:11 GMT, alnsn <21403@news.rsdn.ru> wrote:
>> ME>А зачем этот трюк с умножением на magic32 и последующим сдвигом? Это намного быстрее простого деления? >> >> Наверно ему очень книга www.hackersdelight.org понравилась
ME>
ME>Я хочу узнать действительно ли умножение быстрее деления? Если бы это было сложение и сдвиг, то да, но вот умножение вместо деления...
// test.cint magic(int n)
{
int magic32 = -858993459;
return (magic32*n) >> 1; //division by 10;
}
int divide10(int n)
{
return n / 10;
}
int divide(int n, int m)
{
return n / m;
}
int main()
{
magic(100);
divide10(100);
divide(100, 10);
return 0;
}
$ gcc -O2 test.c
$ objdump -s a.out
08048310 <magic>:
8048310: 55 push %ebp
8048311: 89 e5 mov %esp,%ebp
8048313: 8b 45 08 mov 0x8(%ebp),%eax
8048316: 69 c0 cd cc cc cc imul $0xcccccccd,%eax,%eax
804831c: d1 f8 sar %eax
804831e: 5d pop %ebp
804831f: c3 ret
08048320 <divide10>:
8048320: 55 push %ebp
8048321: 89 e5 mov %esp,%ebp
8048323: 8b 4d 08 mov 0x8(%ebp),%ecx
8048326: 89 c8 mov %ecx,%eax
8048328: ba 67 66 66 66 mov $0x66666667,%edx
804832d: f7 ea imul %edx
804832f: 89 c8 mov %ecx,%eax
8048331: c1 f8 1f sar $0x1f,%eax
8048334: c1 fa 02 sar $0x2,%edx
8048337: 29 c2 sub %eax,%edx
8048339: 89 d0 mov %edx,%eax
804833b: 5d pop %ebp
804833c: c3 ret
804833d: 8d 76 00 lea 0x0(%esi),%esi
08048340 <divide>:
8048340: 55 push %ebp
8048341: 89 e5 mov %esp,%ebp
8048343: 8b 45 08 mov 0x8(%ebp),%eax
8048346: 99 cltd
8048347: f7 7d 0c idivl 0xc(%ebp)
804834a: 5d pop %ebp
804834b: c3 ret
804834c: 8d 74 26 00 lea 0x0(%esi,1),%esi
Re[6]: Как Реализовать atoi без стандартных библиотек
On Wed, 03 Nov 2004 10:55:37 GMT, alnsn <21403@news.rsdn.ru> wrote:
> ME>Я хочу узнать действительно ли умножение быстрее деления? Если бы это было сложение и сдвиг, то да, но вот умножение вместо деления.. > >
