我无法理解以下atoi
实现代码,特别是这一行:
k = (k << 3) + (k << 1) + (*p) - '0';
这是代码:
int my_atoi(char *p) {
int k = 0;
while (*p) {
k = (k << 3) + (k << 1) + (*p) - '0';
p++;
}
return k;
}
有人可以向我解释一下吗?
另一个问题:atof
实现的算法应该是什么?
k = (k << 3) + (k << 1);
手段
k = k * 2³ + k * 2¹ = k * 8 + k * 2 = k * 10
这有帮助吗?
*p - '0'
术语增加了下一个数字的值;这是有效的,因为C要求数字字符具有连续值,以便'1' == '0' + 1
,'2' == '0' + 2
等。
关于你的第二个问题(atof
),这应该是它自己的问题,它是论文的主题,而不是简单的回答......
<<
有点转移,(k<<3)+(k<<1)
是k*10
,由一个认为他比编译器更聪明的人写的(好吧,他错了......)
(*p) - '0'
从0
指向的字符中减去字符p
的值,有效地将字符转换为数字。
我希望你能弄明白其余的......只记得小数系统的工作原理。
这是标准函数atoi
的规范。很抱歉没有引用标准,但这样可以正常工作(来自:http://www.cplusplus.com/reference/clibrary/cstdlib/atoi/)
该函数首先丢弃尽可能多的空白字符(如
isspace
中所示),直到找到第一个非空白字符。然后,从该字符开始,采用可选的初始加号或减号,后跟尽可能多的基数为10的数字,并将它们解释为数值。字符串可以包含在形成整数之后的其他字符,这些字符将被忽略并且对此函数的行为没有影响。
如果
str
中的第一个非空白字符序列不是有效整数,或者由于str
为空或仅包含空格字符而不存在此类序列,则不执行转换并返回零。
#include <stdio.h>
#include <errno.h>
#include <limits.h>
double atof(const char *string);
int debug=1;
int main(int argc, char **argv)
{
char *str1="3.14159",*str2="3",*str3="0.707106",*str4="-5.2";
double f1,f2,f3,f4;
if (debug) printf("convert %s, %s, %s, %s\n",str1,str2,str3,str4);
f1=atof(str1);
f2=atof(str2);
f3=atof(str3);
f4=atof(str4);
if (debug) printf("converted values=%f, %f, %f, %f\n",f1,f2,f3,f4);
if (argc > 1)
{
printf("string %s is floating point %f\n",argv[1],atof(argv[1]));
}
}
double atof(const char *string)
{
double result=0.0;
double multiplier=1;
double divisor=1.0;
int integer_portion=0;
if (!string) return result;
integer_portion=atoi(string);
result = (double)integer_portion;
if (debug) printf("so far %s looks like %f\n",string,result);
/* capture whether string is negative, don't use "result" as it could be 0 */
if (*string == '-')
{
result *= -1; /* won't care if it was 0 in integer portion */
multiplier = -1;
}
while (*string && (*string != '.'))
{
string++;
}
if (debug) printf("fractional part=%s\n",string);
// if we haven't hit end of string, go past the decimal point
if (*string)
{
string++;
if (debug) printf("first char after decimal=%c\n",*string);
}
while (*string)
{
if (*string < '0' || *string > '9') return result;
divisor *= 10.0;
result += (double)(*string - '0')/divisor;
if (debug) printf("result so far=%f\n",result);
string++;
}
return result*multiplier;
}
有趣的是,atoi的手册页并没有表示errno的设置,所以如果你说的是任何数字>(2 ^ 31)-1,你运气不好,同样数字小于-2 ^ 31(假设32 -bit int)。你会得到一个答案,但它不会是你想要的。如果出错,这里可以采用 - ((2 ^ 31)-1)到(2 ^ 31)-1的范围,并返回INT_MIN( - (2 ^ 31))。然后可以检查errno以查看它是否溢出。
#include <stdio.h>
#include <errno.h> /* for errno */
#include <limits.h> /* for INT_MIN */
#include <string.h> /* for strerror */
extern int errno;
int debug=0;
int atoi(const char *c)
{
int previous_result=0, result=0;
int multiplier=1;
if (debug) printf("converting %s to integer\n",c?c:"");
if (c && *c == '-')
{
multiplier = -1;
c++;
}
else
{
multiplier = 1;
}
if (debug) printf("multiplier = %d\n",multiplier);
while (*c)
{
if (*c < '0' || *c > '9')
{
return result * multiplier;
}
result *= 10;
if (result < previous_result)
{
if (debug) printf("number overflowed - return INT_MIN, errno=%d\n",errno);
errno = EOVERFLOW;
return(INT_MIN);
}
else
{
previous_result *= 10;
}
if (debug) printf("%c\n",*c);
result += *c - '0';
if (result < previous_result)
{
if (debug) printf("number overflowed - return MIN_INT\n");
errno = EOVERFLOW;
return(INT_MIN);
}
else
{
previous_result += *c - '0';
}
c++;
}
return(result * multiplier);
}
int main(int argc,char **argv)
{
int result;
printf("INT_MIN=%d will be output when number too high or too low, and errno set\n",INT_MIN);
printf("string=%s, int=%d\n","563",atoi("563"));
printf("string=%s, int=%d\n","-563",atoi("-563"));
printf("string=%s, int=%d\n","-5a3",atoi("-5a3"));
if (argc > 1)
{
result=atoi(argv[1]);
printf("atoi(%s)=%d %s",argv[1],result,(result==INT_MIN)?", errno=":"",errno,strerror(errno));
if (errno) printf("%d - %s\n",errno,strerror(errno));
else printf("\n");
}
return(errno);
}
这是我的实现(成功测试了包含字母,+, - 和零开头的案例)。我试图在Visual Studio中对atoi函数进行逆向工程。如果输入字符串仅包含数字字符,则可以在一个循环中实现。但它变得复杂,因为你应该照顾 - ,+和字母。
int atoi(char *s)
{
int c=1, a=0, sign, start, end, base=1;
//Determine if the number is negative or positive
if (s[0] == '-')
sign = -1;
else if (s[0] <= '9' && s[0] >= '0')
sign = 1;
else if (s[0] == '+')
sign = 2;
//No further processing if it starts with a letter
else
return 0;
//Scanning the string to find the position of the last consecutive number
while (s[c] != '\n' && s[c] <= '9' && s[c] >= '0')
c++;
//Index of the last consecutive number from beginning
start = c - 1;
//Based on sign, index of the 1st number is set
if (sign==-1)
end = 1;
else if (sign==1)
end = 0;
//When it starts with +, it is actually positive but with a different index
//for the 1st number
else
{
end = 1;
sign = 1;
}
//This the main loop of algorithm which generates the absolute value of the
//number from consecutive numerical characters.
for (int i = start; i >=end ; i--)
{
a += (s[i]-'0') * base;
base *= 10;
}
//The correct sign of generated absolute value is applied
return sign*a;
}
关于来自here的atoi()提示代码:
并且基于atoi(),我的atof()实现:
[原始代码有相同的限制,不检查长度等]
double atof(const char* s)
{
double value_h = 0;
double value_l = 0;
double sign = 1;
if (*s == '+' || *s == '-')
{
if (*s == '-') sign = -1;
++s;
}
while (*s >= 0x30 && *s <= 0x39)
{
value_h *= 10;
value_h += (double)(*s - 0x30);
++s;
}
// 0x2E == '.'
if (*s == 0x2E)
{
double divider = 1;
++s;
while (*s >= 0x30 && *s <= 0x39)
{
divider *= 10;
value_l *= 10;
value_l += (double)(*s - 0x30);
++s;
}
return (value_h + value_l/divider) * sign;
}
else
{
return value_h * sign;
}
}