校园招聘
您要查看的是:网易面试,问atoi实现的效率改进问题
(酷讯和网页http://silver6.itpub.net/post/7329/45372的作者无关,与网易面试,问atoi实现的效率改进问题该文的作者无关,不对网易面试,问atoi实现的效率改进问题的内容负责。)
毛泽西 | 网易面试,问atoi实现的效率改进问题

This page looks plain and unstyled because you're using a non-standard compliant browser. To see it in its best form, please upgrade to a browser that supports web standards. It's free and painless.

毛泽西

首页 | 资源中心 | 管理控制台

« | »

网易面试,问atoi实现的效率改进问题

silver6 | 10 十一月, 2005 08:58

今天去一面,面试官云风要我把笔试时做的atoi实现改进一下,我想了半天,终于想出一点,即确定某字符所在的万、千、百、十位后,本来是循环乘10,我说可以做一个数组里面就放上10000,1000,100,10,1,找到位数后直接索引再乘那个字符,这样多次乘法就减为一次了。可是云风说还可以改进,然后提示除了在数组里放上10000,1000,100,10,1之外还可以放别的数,甚至多位一起乘,当时真是紧张,完全没明白!
哪位高手指点一下?要是还有二面,我就好答了。我先去debug一下tc库里atoi的实现吧,等看懂了再来帖~

这是我刚开始学C++的时候,不知道C++里有可以把字符串转换成数字的函数是什么时,自己写的一个函数:
int strtoint(string s)
{
if (s[0] != '-')
{
s = "+" + s;
}
int n = 0;
for(int i = 1, l = s.size();i < l;i++)
{
if ((s[i] > 57)||(s[i] < 48))
{
cerr << "Please enter integrity!" << 'n';
system("pause");
exit(1);
}
n = n * 10 + (s[i] - 48);
}
if (s[0] == '-')
n = -1 * n;
return n;
}

最简单的是调试跟进去,前提是你已经安装了CRT的源代码,我VC7看到的代码是这样的:
long __cdecl _tstol(
const _TCHAR *nptr
)
{
int c; /* current char */
long total; /* current total */
int sign; /* if '-', then negative, otherwise positive */
#if defined (_MT) && !defined (_UNICODE)
pthreadlocinfo ptloci = _getptd()->ptlocinfo;

if ( ptloci != __ptlocinfo )
ptloci = __updatetlocinfo();

/* skip whitespace */
while ( __isspace_mt(ptloci, (int)(_TUCHAR)*nptr) )
#else /* defined (_MT) && !defined (_UNICODE) */
while ( _istspace((int)(_TUCHAR)*nptr) )
#endif /* defined (_MT) && !defined (_UNICODE) */
++nptr;

c = (int)(_TUCHAR)*nptr++;
sign = c; /* save sign indication */
if (c == _T('-') || c == _T('+'))
c = (int)(_TUCHAR)*nptr++; /* skip sign */

total = 0;

while ( (c = _tchartodigit(c)) != -1 ) {
total = 10 * total + c; /* accumulate digit */
c = (_TUCHAR)*nptr++; /* get next char */
}

if (sign == '-')
return -total;
else
return total; /* return result, negated if necessary */
}

#define _tchartodigit(c) ((c) >= '0' && (c) <= '9' ? (c) - '0' : -1)

int StrToInt(char* str)
{
int total=0;
while(*str != 0)
{
total = total * 10 + (int)(*str - '0');
}
return total;
}

long __cdecl atol(
const char *nptr
)
{
int c; /* current char */
long total; /* current total */
int sign; /* if '-', then negative, otherwise positive */

/* skip whitespace */
while ( isspace((int)(unsigned char)*nptr) )
++nptr;

c = (int)(unsigned char)*nptr++;
sign = c; /* save sign indication */
if (c == '-' || c == '+')
c = (int)(unsigned char)*nptr++; /* skip sign */

total = 0;

while (isdigit(c)) {
total = 10 * total + (c - '0'); /* accumulate digit */
c = (int)(unsigned char)*nptr++; /* get next char */
}

if (sign == '-')
return -total;
else
return total; /* return result, negated if necessary */
}

vc6下的源码。 atoi 也是调用 atol


发表评论

标题

在此添加评论

称呼

邮箱地址(可选)

个人主页(可选)




Valid XHTML 1.0 Strict and CSS.
Powered by pLog
Design by Book of Styles