2025年5月18日 星期日 9:24am

atoi(c89)

相关文章:

C89中的说明

头文件

stdlib.h

函数原型

int atoi(const char *nptr);

nptr: 指向待转换的字符串的指针

返回值

字串的整型形式, 必须以NULL结尾.

说明

atoi函数跳过字串开头的所有空白字符, 转换接下来的数字字符, 遇到第一个非数字字符停止

c11中的相关说明

C11的标准中关于atoi的描述为:

当遇到错误时, atoi不需要(need not)改变errno的值, 当值的结果无法表示时, 行为是未定义的.

除了错误处理外, 它等价于(equivalent): (int)strtol(nptr, (char **)NULL, 10)

关于strtol函数, 我会单独介绍(文章的占位符在这里).

我的实现

第一次尝试: 菜鸟版

实现"字符串转换成整数"函数, 始于庞果网上的一道题. 题目并没有太多的文字描述, 不过它给了一系列输入及预期的输出(筛选其中的一部分), 条件是在32位的系统上:

输入             输出
""               0
"1"              1
"-1"             -1
"123"            123
"-123"           -123
"010"            10
"+00131204"      131204
"2147483647"     2147483647
"2147483648"     2147483647
"-2147483648"    -2147483648
"-2147483649"    -2147483648
"23a8f"          23
"  +4488 "       4488
"abc"            0
" - 321"         0
" ++1"           0

从以上数据, 可以分析出以下几点:

1. 空字串("")或非法字串(如"abc"), 输出0;

2. 可以有符号(如"123"), 也可以没有(如"-123"), 如果有符号, 则符号后面必须是数字, 符号与数字之间不能有空格;

3. 开头的空格将被过滤, 末尾的空格也不会管;

4. 数字前面的字符'0'将被过滤(如"010");

5. 如果超过最大值(如"2147483648"), 则输出最大值2147483647(32位的最大int值); 如果超过最小值(如"-2147483649"), 则输出最小值-2147483648(32位的最小int值);

个人觉得以上的例子不太充分, 于是举出另一批例子对gcc的atoi函数进行测试, 以下为结果:

输入                      输出
"\n\r\t\v 123\n\r\t\v "  123
"0+123"                  0

于是可以对上面的第3条和第4条进行补充:

3.1 不只是空格, 开头和末尾的所有空白字符(isspace)都将被过滤.

4.1 开头的字符'0'并不会被当作空白字符那样被过滤. 可以想像到, 读到任意数字(如这里的'0')之后的非数字(如这里的'+'), 都将停止.

以下是当时提交的代码:

  1. //atoi version1
  2. int StrToInt(const char* str)
  3. {
  4.     static const int MAX = (int)((unsigned)~0 >> 1);
  5.     static const int MIN = -(int)((unsigned)~0 >> 1) - 1;
  6.     unsigned int n = 0;
  7.     int sign = 1;
  8.  
  9.     while (isspace(*str))
  10.         ++str;
  11.     if (*str == '+' || *str == '-')
  12.     {
  13.         if (*str == '-')
  14.             sign = -1;
  15.         ++str;
  16.     }
  17.     while (isdigit(*str))
  18.     {
  19.         n = n * 10 + (*str-'0');
  20.         ++str;
  21.     }
  22.     if (sign > 0 && (unsigned)n > (unsigned)MAX)
  23.     {
  24.         n = MAX;
  25.     }
  26.     else if (sign < 0)
  27.     {
  28.         if ((unsigned)n > (unsigned)MIN)
  29.             n = MIN;
  30.         else
  31.             n = -n;
  32.     }
  33.     return n;
  34. }

测试结果:

input                      output
"1"                        1
"-1"                       -1
"123"                      123
"-123"                     -123
"010"                      10
"+00131204"                131204
"2147483647"               2147483647
"2147483648"               2147483647
"-2147483648"              -2147483648
"-2147483649"              -2147483648
"23a8f"                    23
"  +4488 "                 4488
"abc"                      0
" - 321"                   0
" ++1"                     0
"\n\r\t\v 123\n\r\t\v "    0

貌似测试结果没有啥错误(最后一行输出为0呀! fixme!). 但是如果一个很大的数字让语句"n = n * 10 + (*str-'0');"溢出, 会怎么样呢?

input             output
"10522545459"     1932610867
"-10522545459"    -1932610867

bingo! 读完倒数第二个数字5后, 还没有溢出, n的值为1052254545(0x3EB8 2151), 但是乘以10再加9呢? 溢出了(0x2 7331 4D2A), n的值为1932610858(丢掉溢出的高位后变成:0x7331 4D2A), 1932610858是小于MAX的, 程序认为没有溢出.

联想到另一个问题: 判断两个正整数相加是否溢出, 一般可以用以下的方法(假设a和b是int类型变量):

  1. if ((unsigned)a + (unsigned)b > INT_MAX)
  2.     complain();

如果将加法转换成减法, 可以不用将a和b转换成unsigned:

  1. if (a > INT_MAX - b)
  2.     complain();

那么, 这里的乘法是否也可以用相同的方法进行改进呢? 请君思考.

第二次尝试: 提高溢出处理的健壮性,除法代替乘法

在拜读了该网站的作者v_JULY_v君的文章《程序员编程艺术第三十~三十一章：字符串转换成整数，通配符字符串匹配》后, 对于溢出的处理, 我觉得可以作如下的改进:

既然一个数括大10倍, 有可能溢出, 而且很难判断是否溢出, 为什么不用除法呢? 与其将n扩大10倍, 冒着溢出的风险, 再与MAX进行比较(如果已经溢出, 则比较的结果没有意义), 不如先用n与MAX/10进行比较: 若n>MAX/10(还要考虑n=MAX/10的情况), 说明将要溢出了, 此时可以很明智地下结论: 溢出, 然后进行溢出处理(如返回最大值).

以下为实现代码:

(实现前的说明)

1. MAX不用2147483647的原因: 有可能将来int类型不是4字节, 即使扩展成8个字节, 程序也应该正常运行.

2. 请允许我把函数名改为StrToDecInt, 因为本函数只处理10进制整数.(即使字串中包含"081"这种类型, 也认为是十进制的81, 而不是八进制的081)

  1. //atoi version2:replace multiplication with division
  2. int StrToDecInt(const char* str)
  3. {
  4.     static const int MAX = (int)((unsigned)~0 >> 1);
  5.     static const int MIN = -(int)((unsigned)~0 >> 1) - 1;
  6.     int n = 0;
  7.     int sign = 1;
  8.     int c;
  9.  
  10.     while (isspace(*str))
  11.         ++str;
  12.     if (*str == '+' || *str == '-')
  13.     {
  14.         if (*str == '-')
  15.             sign = -1;
  16.         ++str;
  17.     }
  18.     while (isdigit(*str))
  19.     {
  20.         c = *str - '0';
  21.         if (sign > 0 && (n > MAX/10 || (n == MAX/10 && c >= MAX%10)))
  22.         {
  23.             n = MAX;
  24.             break;
  25.         }
  26.         else if (sign < 0 && (n > (unsigned)MIN/10 
  27.                               || (n == (unsigned)MIN/10 && c >= (unsigned)MIN%10)))
  28.         {
  29.             n = MIN;
  30.             break;
  31.         }
  32.         n = n * 10 + c;
  33.         ++str;
  34.     }
  35.     return sign > 0 ? n : -n;
  36. }

测试结果(vs2010):

input                      output
"1"                        1
"-1"                       -1
"123"                      123
"-123"                     -123
"010"                      10
"+00131204"                131204
"2147483647"               2147483647
"2147483648"               2147483647
"10522545459"              2147483647
"-2147483648"              -2147483648
"-2147483649"              -2147483648
"-10522545459"             -2147483648
"23a8f"                    23
"  +4488 "                 4488
"abc"                      0
" - 321"                   0
" ++1"                     0
"\n\r\t\v 123\n\r\t\v "    0

(最后一行输出为0呀! fixme!)

第三次尝试: 修复隐藏的bug

第二次尝试中的代码是完美的吗? No. 感谢Apostate(他的空间)在v_JULY_v君的文章《程序员编程艺术第三十~三十一章：字符串转换成整数，通配符字符串匹配》中的评论, 他指出:

1. 如果n为MIN, 则-n是溢出的(虽然溢出, 输出为什么还是正确的呢? fixme!).

我觉得还有以下可以改进的地方:

2. MAX和MIN变量是多余的, 可以直接使用limits.h中的INT_MAX和INT_MIN.

3. 可以考虑将MAX/10, MAX%10, MIN/10和MIN%10保存为临时变量. (有必要吗? your advice?)

4. 减少不必要的赋值: 可以考虑用char类型的变量sign来保存第一个非空格字符, 来表示数字的符号, 用sign跟'-'比较.

修改后代码:

  1. //atoi version3: improving version2
  2. int atoi_mjn(const char* str) {
  3.     int n = 0;
  4.     char sign;
  5.     int c;
  6.  
  7.     while (isspace(*str))
  8.         ++str;
  9.  
  10.     sign = *str;
  11.     if (sign == '+' || sign == '-')
  12.         ++str;
  13.  
  14.     while (isdigit(*str))
  15.     {
  16.         c = *str - '0';
  17.         if (sign != '-' && (n > INT_MAX/10 || (n == INT_MAX/10 && c >= INT_MAX%10)))
  18.         {
  19.             return INT_MAX;
  20.         }
  21.         else if (sign == '-' && (n > (unsigned)INT_MIN/10 
  22.                               || (n == (unsigned)INT_MIN/10 && c >= (unsigned)INT_MIN%10)))
  23.         {
  24.             return INT_MIN;
  25.         }
  26.         n = n * 10 + c;
  27.         ++str;
  28.     }
  29.     return sign == '-' ? -n : n;
  30. }

测试结果与尝试二的相同, 不再贴出.

atoi的实现

参考wikibooks:http://en.wikibooks.org/wiki/C_Programming/C_Reference/stdlib.h/atoi

Nut/OS的实现

atoi函数调用strtol函数, 源码如下(或见原页面):

  1. int atoi(CONST char *str)
  2. {
  3.     return ((int) strtol(str, (char **) NULL, 10));
  4. }

strtol实现的思想跟我写的第二段代码有点像(除法代替乘法). 如下(或见 原页面): 

  1. long strtol(CONST char *nptr, char **endptr, int base)
  2. {
  3.     register CONST char *s;
  4.     register long acc, cutoff;
  5.     register int c;
  6.     register int neg, any, cutlim;
  7.  
  8.     /*
  9.      * Skip white space and pick up leading +/- sign if any.
  10.      * If base is 0, allow 0x for hex and 0 for octal, else
  11.      * assume decimal; if base is already 16, allow 0x.
  12.      */
  13.     s = nptr;
  14.     do {
  15.         c = (unsigned char) *s++;
  16.     } while (isspace(c));
  17.     if (c == '-') {
  18.         neg = 1;
  19.         c = *s++;
  20.     } else {
  21.         neg = 0;
  22.         if (c == '+')
  23.             c = *s++;
  24.     }
  25.     if ((base == 0 || base == 16) && c == '0' && (*s == 'x' || *s == 'X')) {
  26.         c = s[1];
  27.         s += 2;
  28.         base = 16;
  29.     }
  30.     if (base == 0)
  31.         base = c == '0' ? 8 : 10;
  32.  
  33.     /*
  34.      * Compute the cutoff value between legal numbers and illegal
  35.      * numbers.  That is the largest legal value, divided by the
  36.      * base.  An input number that is greater than this value, if
  37.      * followed by a legal input character, is too big.  One that
  38.      * is equal to this value may be valid or not; the limit
  39.      * between valid and invalid numbers is then based on the last
  40.      * digit.  For instance, if the range for longs is
  41.      * [-2147483648..2147483647] and the input base is 10,
  42.      * cutoff will be set to 214748364 and cutlim to either
  43.      * 7 (neg==0) or 8 (neg==1), meaning that if we have accumulated
  44.      * a value > 214748364, or equal but the next digit is > 7 (or 8),
  45.      * the number is too big, and we will return a range error.
  46.      *
  47.      * Set any if any `digits' consumed; make it negative to indicate
  48.      * overflow.
  49.      */
  50.     cutoff = neg ? LONG_MIN : LONG_MAX;
  51.     cutlim = cutoff % base;
  52.     cutoff /= base;
  53.     if (neg) {
  54.         if (cutlim > 0) {
  55.             cutlim -= base;
  56.             cutoff += 1;
  57.         }
  58.         cutlim = -cutlim;
  59.     }
  60.     for (acc = 0, any = 0;; c = (unsigned char) *s++) {
  61.         if (isdigit(c))
  62.             c -= '0';
  63.         else if (isalpha(c))
  64.             c -= isupper(c) ? 'A' - 10 : 'a' - 10;
  65.         else
  66.             break;
  67.         if (c >= base)
  68.             break;
  69.         if (any < 0)
  70.             continue;
  71.         if (neg) {
  72.             if ((acc < cutoff || acc == cutoff) && c > cutlim) {
  73.                 any = -1;
  74.                 acc = LONG_MIN;
  75.                 errno = ERANGE;
  76.             } else {
  77.                 any = 1;
  78.                 acc *= base;
  79.                 acc -= c;
  80.             }
  81.         } else {
  82.             if ((acc > cutoff || acc == cutoff) && c > cutlim) {
  83.                 any = -1;
  84.                 acc = LONG_MAX;
  85.                 errno = ERANGE;
  86.             } else {
  87.                 any = 1;
  88.                 acc *= base;
  89.                 acc += c;
  90.             }
  91.         }
  92.     }
  93.     if (endptr != 0)
  94.         *endptr = (char *) (any ? s - 1 : nptr);
  95.     return (acc);
  96. }

linux内核的实现

atoi是C语言标准库的函数, 但是系统内核也有这种需求(源文件见这里, 关于此函数的测试, 请见另一篇文章"字符串转换成整数: linux内核atoi函数的测试"):

  1. /*
  2.  *  ======== atoi ========
  3.  *  Purpose:
  4.  *      This function converts strings in decimal or hex format to integers.
  5.  */
  6. static s32 atoi(char *psz_buf)
  7. {
  8.         char *pch = psz_buf;
  9.         s32 base = 0;
  10.  
  11.         while (isspace(*pch))
  12.                 pch++;
  13.  
  14.         if (*pch == '-' || *pch == '+') {
  15.                 base = 10;
  16.                 pch++;
  17.         } else if (*pch && tolower(pch[strlen(pch) - 1]) == 'h') {
  18.                 base = 16;
  19.         }
  20.  
  21.         return simple_strtoul(pch, NULL, base);
  22. }
其中s32是signed int的别名. atoi调用了simple_strtoul, 其返回值是unsigned long, atoi在返回时, 强制转换成int, 而不管结果是否正确(很显然这个atoi不安全). 现在看一下 simple_strtoul函数: 

  1. /**
  2.  * simple_strtoul - convert a string to an unsigned long
  3.  * @cp: The start of the string
  4.  * @endp: A pointer to the end of the parsed string will be placed here
  5.  * @base: The number base to use
  6.  *
  7.  * This function is obsolete. Please use kstrtoul instead.
  8.  */
  9. unsigned long simple_strtoul(const char *cp, char **endp, unsigned int base)
  10. {
  11.         return simple_strtoull(cp, endp, base);
  12. }
直接进入 simple_strtoull: 

  1. /**
  2.  * simple_strtoull - convert a string to an unsigned long long
  3.  * @cp: The start of the string
  4.  * @endp: A pointer to the end of the parsed string will be placed here
  5.  * @base: The number base to use
  6.  *
  7.  * This function is obsolete. Please use kstrtoull instead.
  8.  */
  9. unsigned long long simple_strtoull(const char *cp, char **endp, unsigned int base)
  10. {
  11.         unsigned long long result;
  12.         unsigned int rv;
  13.  
  14.         cp = _parse_integer_fixup_radix(cp, &base);
  15.         rv = _parse_integer(cp, base, &result);
  16.         /* FIXME */
  17.         cp += (rv & ~KSTRTOX_OVERFLOW);
  18.  
  19.         if (endp)
  20.                 *endp = (char *)cp;
  21.  
  22.         return result;
  23. }
函数 _parse_integer_fixup_radix主要用来设置基数(8,10,16进制?), 且过滤前面的"0x"(如果有的话), 函数的注释也明确说明了: 该函数已废弃, 请使用 kstrtoull. 转换工作主要在 _parse_integer, 转换的整数在参数result中, 函数返回数字字符的个数: 
  1. /*
  2.  * Convert non-negative integer string representation in explicitly given radix
  3.  * to an integer.
  4.  * Return number of characters consumed maybe or-ed with overflow bit.
  5.  * If overflow occurs, result integer (incorrect) is still returned.
  6.  *
  7.  * Don't you dare use this function.
  8.  */
  9. unsigned int _parse_integer(const char *s, unsigned int base, unsigned long long *p)
  10. {
  11.         unsigned long long res;
  12.         unsigned int rv;
  13.         int overflow;
  14.  
  15.         res = 0;
  16.         rv = 0;
  17.         overflow = 0;
  18.         while (*s) {
  19.                 unsigned int val;
  20.  
  21.                 if ('0' <= *s && *s <= '9')
  22.                         val = *s - '0';
  23.                 else if ('a' <= _tolower(*s) && _tolower(*s) <= 'f')
  24.                         val = _tolower(*s) - 'a' + 10;
  25.                 else
  26.                         break;
  27.  
  28.                 if (val >= base)
  29.                         break;
  30.                 /*
  31.                  * Check for overflow only if we are within range of
  32.                  * it in the max base we support (16)
  33.                  */
  34.                 if (unlikely(res & (~0ull << 60))) {
  35.                         if (res > div_u64(ULLONG_MAX - val, base))
  36.                                 overflow = 1;
  37.                 }
  38.                 res = res * base + val;
  39.                 rv++;
  40.                 s++;
  41.         }
  42.         *p = res;
  43.         if (overflow)
  44.                 rv |= KSTRTOX_OVERFLOW;
  45.         return rv;
  46. }

unlikely是一个没有实际作用的宏:

#define unlikely(cond) (cond)

正如它的字面意思, 告诉看代码的人: 这里不太可能发生(或不太经常发生), 因为要输入大于等于1152921504606846976(16进制为0x1000000000000000)的数, if条件才会成立.

x86的CPU, unsigned long long占8个字节, 表示式~0ull << 60的值为0xf000000000000000, 该函数最大支持的基数是16, 所以下次要左移4位, 对于0x10000000000000001(注意这里多了一位)这个数字, 在读取到最后一个数字'1'的时候, 程序会检测溢出, 但是程序继续执行, 结果是错误的.

我的实现与linux内核的atoi函数的实现, 都有一个共同的问题: 即使出错, 函数也返回了一个值, 导致调用者误认为自己传入的参数是正确的, 但是可能会导致程序的其他部分产生莫名的错误且很难调试.

其他实现

waterloo | cheriton school of computer science: atoi

References:

  1. v_JULY_v: 程序员编程艺术第三十~三十一章：字符串转换成整数，通配符字符串匹配
  2. Nut/OS API
  3. Linux Cross Reference
文章知识点与官方知识档案匹配，可进一步学习相关知识
C技能树首页概览156652 人正在系统学习中
注：本文转载自blog.csdn.net的MJN的文章"http://blog.csdn.net/njnu_mjn/article/details/9099405"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！