字符串转换为整数

时间:2023-01-07 09:12:45

第三十章、字符串转换成整数

    先看题目:

    输入一个表示整数的字符串,把该字符串转换成整数并输出,例如输入字符串"345",则输出整数345。
给定函数原型int StrToInt(const char *str) ,完成函数StrToInt,实现字符串转换成整数的功能,不得用库函数atoi(即便准许使用,其对于溢出情况的处理也达不到题目的要求,详情请参看下文第7节末)。

    我们来一步一步分析(9小节,重点在下文第8小节及后续内容),直至写出第一份准确的代码:

1、本题考查的实际上就是字符串转换成整数的问题,或者说是要你自行实现atoi函数。那如何实现把表示整数的字符串正确地转换成整数呢?以"345"作为例子:

  1. 当我们扫描到字符串的第一个字符'3'时,由于我们知道这是第一位,所以得到数字3。
  2. 当扫描到第二个数字'4'时,而之前我们知道前面有一个3,所以便在后面加上一个数字4,那前面的3相当于30,因此得到数字:3*10+4=34。
  3. 继续扫描到字符'5','5'的前面已经有了34,由于前面的34相当于340,加上后面扫描到的5,最终得到的数是:34*10+5=345。

    因此,此题的思路便是:每扫描到一个字符,我们便把在之前得到的数字乘以10,然后再加上当前字符表示的数字

    2、思路有了,有一些细节需要注意,如zhedahht所说:

  1. 由于整数可能不仅仅之含有数字,还有可能以'+'或者'-'开头,表示整数的正负。因此我们需要把这个字符串的第一个字符做特殊处理。如果第一个字符是'+'号,则不需要做任何操作;如果第一个字符是'-'号,则表明这个整数是个负数,在最后的时候我们要把得到的数值变成负数。
  2. 接着我们试着处理非法输入。由于输入的是指针,在使用指针之前,我们要做的第一件是判断这个指针是不是为空。如果试着去访问空指针,将不可避免地导致程序崩溃。
  3. 另外,输入的字符串中可能含有不是数字的字符。每当碰到这些非法的字符,我们就没有必要再继续转换。
  4. 最后一个需要考虑的问题是溢出问题。由于输入的数字是以字符串的形式输入,因此有可能输入一个很大的数字转换之后会超过能够表示的最大的整数而溢出。
    比如,当给的字符串是如左边图片所示的时候,有考虑到么?当然,它们各自对应的正确输出如右边图片所示( 假定你是在32位系统下,且编译环境是VS2008以上):
字符串转换为整数 字符串转换为整数
    3、很快,可能你就会写下如下代码:
  1. //copyright@zhedahht 2007     
  2. enum Status {kValid = 0, kInvalid};  
  3. int g_nStatus = kValid;  
  4.   
  5. // Convert a string into an integer   
  6. int StrToInt(const char* str)  
  7. {  
  8.     g_nStatus = kInvalid;  
  9.     long long num = 0;  
  10.   
  11.     if(str != NULL)  
  12.     {  
  13.         const char* digit = str;  
  14.   
  15.         // the first char in the string maybe '+' or '-'   
  16.         bool minus = false;  
  17.         if(*digit == '+')  
  18.             digit ++;  
  19.         else if(*digit == '-')  
  20.         {  
  21.             digit ++;  
  22.             minus = true;  
  23.         }  
  24.   
  25.         // the remaining chars in the string   
  26.         while(*digit != '\0')  
  27.         {  
  28.             if(*digit >= '0' && *digit <= '9')  
  29.             {  
  30.                 num = num * 10 + (*digit - '0');  
  31.   
  32.                 // overflow     
  33.                 if(num > std::numeric_limits<int>::max())  
  34.                 {  
  35.                     num = 0;  
  36.                     break;  
  37.                 }  
  38.   
  39.                 digit ++;  
  40.             }  
  41.             // if the char is not a digit, invalid input   
  42.             else  
  43.             {  
  44.                 num = 0;  
  45.                 break;  
  46.             }  
  47.         }  
  48.   
  49.         if(*digit == '\0')  
  50.         {  
  51.             g_nStatus = kValid;  
  52.             if(minus)  
  53.                 num = 0 - num;  
  54.         }  
  55.     }  
  56.     return static_cast<int>(num);  
  57. }  
    run下上述程序,会发现当输入字符串是下图中红叉叉部分所对应的时候,程序结果出错:  
     字符串转换为整数

    两个问题:

  1. 当输入的字符串不是数字,而是字符的时候,比如“1a”,上述程序直接返回了0(而正确的结果应该是得到1):
    1. // if the char is not a digit, invalid input   
    2.                   else  
    3.                   {  
    4.                       num = 0;  
    5.                       break;  
    6.                   }  
  2. 处理溢出时,有问题。因为它遇到溢出情况时,直接返回了0:
    1. // overflow     
    2.                 if(num > std::numeric_limits<int>::max())  
    3.                 {  
    4.                     num = 0;  
    5.                     break;  
    6.                 }  

    4、把代码做下微调,如下( 注:库函数atoi规定超过int值,按最大值maxint:2147483647来,超过-int按最小值minint:-2147483648来):
  1. //copyright@SP_daiyq 2013/5/29   
  2. int StrToInt(const char* str)  
  3. {  
  4.     int res = 0; // result   
  5.     int i = 0; // index of str   
  6.     int signal = '+'// signal '+' or '-'   
  7.     int cur; // current digit   
  8.   
  9.     if (!str)  
  10.         return 0;  
  11.   
  12.     // skip backspace   
  13.     while (isspace(str[i]))  
  14.         i++;  
  15.   
  16.     // skip signal   
  17.     if (str[i] == '+' || str[i] == '-')  
  18.     {  
  19.         signal = str[i];  
  20.         i++;  
  21.     }  
  22.   
  23.     // get result   
  24.     while (str[i] >= '0' && str[i] <= '9')  
  25.     {  
  26.         cur = str[i] - '0';  
  27.   
  28.         // judge overlap or not   
  29.         if ( (signal == '+') && (cur > INT_MAX - res*10) )  
  30.         {  
  31.             res = INT_MAX;  
  32.             break;  
  33.         }  
  34.         else if ( (signal == '-') && (cur -1 > INT_MAX - res*10) )  
  35.         {  
  36.             res = INT_MIN;  
  37.             break;  
  38.         }  
  39.   
  40.         res = res * 10 + cur;  
  41.         i++;  
  42.     }  
  43.   
  44.     return (signal == '-') ? -res : res;  
  45. }  
    此时会发现,上面第3小节末所述的第1个小问题( 当输入的字符串不是数字,而是字符的时候)解决了:
     字符串转换为整数
    但, 上文第3小节末所述的第2个小问题:溢出问题却没有解决。即当给定下述测试数据的时候,问题就来了:
需要转换的字符串                           代码运行结果    理应得到的正确结果
     字符串转换为整数
    什么问题呢?比如说用上述代码转换这个字符串:"    10522545459",它本应得到的正确结果应该是2147483647,但程序实际得到的结果却是:1932610867。故很明显,程序没有解决好上面的第2个小问题:溢出问题。原因是什么呢?咱们来分析下代码,看是如何具体处理溢出情况的:
  1. // judge overlap or not   
  2.         if ( (signal == '+') && (cur > INT_MAX - res*10) )  
  3.         {  
  4.             res = INT_MAX;  
  5.             break;  
  6.         }  
  7.         else if ( (signal == '-') && (cur -1 > INT_MAX - res*10) )  
  8.         {  
  9.             res = INT_MIN;  
  10.             break;  
  11.         }  
    接着上面的例子来,比如给定字符串"    10522545459",除去空格有11位,而MAX_INT,即2147483647是10位数,当扫描到最后一个字符‘9’的时候,程序会比较  92147483647 - 1052254545*10的大小。
     问题立马就暴露出来了,因为此时让res*10,即让1052254545*10 > MAX_INT,溢出无疑,程序已经出错,再执行下面这行代码已无意义:
  1. cur > INT_MAX - res*10  
    也就是说, 对于字符串"10522545459",  当扫描到最后一个字符‘9’时,根据上文第1小节的字符串转换成整数的思路:“每扫描到一个字符,我们便把在之前得到的数字乘以10,然后再加上当前字符表示的数字”,为了得到最终的整数,我们得如此计算:

1052254545*10 + 4,

    然实际上当程序计算到1052254545*10时,

1052254545*10 >

2147483647

    此时已经溢出了,若再执意计算,则程序逻辑将出错,故此后也就不能再判断字串的最后一位4是否大于2147483647%10了(耐不得烦想尽快看到最终正确代码的读者可以直接跳到下文第8节)。

  
    5、上面说给的程序没有“ 很好的解决溢出问题。由于输入的数字是以字符串的形式输入,因此有可能输入一个很大的数字转换之后会超过能够表示的最大的整数而溢出”。那么,到底代码该如何写呢?
    像下面这样?:
  1. //copyright@fuwutu 2013/5/29   
  2. int StrToInt(const char* str)  
  3. {  
  4.     bool negative = false;  
  5.     long long result = 0;  
  6.     while (*str == ' ' || *str == '\t')  
  7.     {  
  8.         ++str;  
  9.     }  
  10.     if (*str == '-')  
  11.     {  
  12.         negative = true;  
  13.         ++str;  
  14.     }  
  15.     else if (*str == '+')  
  16.     {  
  17.         ++str;  
  18.     }  
  19.   
  20.     while (*str != '\0')  
  21.     {  
  22.         int n = *str - '0';  
  23.         if (n < 0 || n > 9)  
  24.         {  
  25.             break;  
  26.         }  
  27.   
  28.         if (negative)  
  29.         {  
  30.             result = result * 10 - n;  
  31.             if (result < -2147483648LL)  
  32.             {  
  33.                 result = -2147483648LL;  
  34.             }  
  35.         }  
  36.         else  
  37.         {  
  38.             result = result * 10 + n;  
  39.             if (result > 2147483647LL)  
  40.             {  
  41.                 result = 2147483647LL;  
  42.             }  
  43.         }  
  44.         ++str;  
  45.     }  
  46.   
  47.   return result;  
  48. }  
    run下程序,看看运行结果:
     字符串转换为整数
     上图所示程序貌似通过了,然实际上它还是未能处理数据溢出的问题,因为它只是做了个取巧,即把返回的值esult定义成了long long,如下所示:
  1. long long result = 0;  
    故严格说来,我们依然未写出准确的规范代码。

    6 那到底该如何解决这个数据溢出的问题呢?咱们先来看看Microsoft是如何实现atoi的吧:
  1. //atol函数   
  2. //Copyright (c) 1989-1997, Microsoft Corporation. All rights reserved.   
  3. long __cdecl atol(  
  4.     const char *nptr  
  5.     )  
  6. {  
  7.     int c; /* current char */  
  8.     long total; /* current total */  
  9.     int sign; /* if ''-'', then negative, otherwise positive */  
  10.   
  11.     /* skip whitespace */  
  12.     while ( isspace((int)(unsigned char)*nptr) )  
  13.         ++nptr;  
  14.   
  15.     c = (int)(unsigned char)*nptr++;  
  16.     sign = c; /* save sign indication */  
  17.     if (c == ''-'' || c == ''+'')  
  18.         c = (int)(unsigned char)*nptr++; /* skip sign */  
  19.   
  20.     total = 0;  
  21.   
  22.     while (isdigit(c)) {  
  23.         total = 10 * total + (c - ''0''); /* accumulate digit */  
  24.         c = (int)(unsigned char)*nptr++; /* get next char */  
  25.     }  
  26.   
  27.     if (sign == ''-'')  
  28.         return -total;  
  29.     else  
  30.         return total; /* return result, negated if necessary */  
  31. }  
    其中,isspace和isdigit函数的实现代码为:
  1. isspace(int x)    
  2. {    
  3.     if(x==' '||x=='/t'||x=='/n'||x=='/f'||x=='/b'||x=='/r')    
  4.         return 1;    
  5.     else     
  6.         return 0;    
  7. }    
  8.   
  9. isdigit(int x)    
  10. {    
  11.     if(x<='9'&&x>='0')             
  12.         return 1;     
  13.     else     
  14.         return 0;    
  15. }   
    然后 atoi调用上面的atol函数,如下所示:
  1. //atoi调用上述的atol   
  2. int __cdecl atoi(  
  3.     const char *nptr  
  4.     )  
  5. {  
  6.     //Overflow is not detected. Because of this, we can just use   
  7.     return (int)atol(nptr);  
  8. }  

    但很遗憾的是,上述atoi标准代码依然返回的是long:

  1. long total; /* current total */  
  2. if (sign == ''-'')  
  3.     return -total;  
  4. else  
  5.     return total; /* return result, negated if necessary */  

    再者,下面这里定义成long的total与10相乘,即total*10很容易溢出:

  1. long total; /* current total */  
  2. total = 10 * total + (c - ''0''); /* accumulate digit */  
   最后,根据本文评论下的读者meiyuli反应:“测试数据是字符串"-21474836480",api算出来的是-2147483648,用上述代码算出来的结果是0”,如此,上述微软的这个atoi源码是有问题的。

     7 microsoft既然不行,读者想必很自然的想到linux。So,咱们接下来便看看 linux内核中是如何实现此字符串转换为整数的问题的。linux内核中提供了以下几个函数:
  1. simple_strtol,把一个字符串转换为一个有符号长整数;
  2. simple_strtoll,把一个字符串转换为一个有符号长长整数;
  3. simple_strtoul,把一个字符串转换为一个无符号长整数;
  4. simple_strtoull,把一个字符串转换为一个无符号长长整数
    相关源码及分析如下。
    首先,atoi调下面的strtol:
  1. //linux/lib/vsprintf.c   
  2. //Copyright (C) 1991, 1992  Linus Torvalds   
  3. //simple_strtol - convert a string to a signed long   
  4. long simple_strtol(const char *cp, char **endp, unsigned int base)  
  5. {  
  6.     if (*cp == '-')  
  7.         return -simple_strtoul(cp + 1, endp, base);  
  8.   
  9.     return simple_strtoul(cp, endp, base);  
  10. }  
  11. EXPORT_SYMBOL(simple_strtol);  
    然后,上面的strtol调下面的strtoul:
  1. //simple_strtoul - convert a string to an unsigned long   
  2. unsigned long simple_strtoul(const char *cp, char **endp, unsigned int base)  
  3. {  
  4.     return simple_strtoull(cp, endp, base);  
  5. }  
  6. EXPORT_SYMBOL(simple_strtoul);  
    接着,上面的strtoul调下面的strtoull:
  1. //simple_strtoll - convert a string to a signed long long   
  2. long long simple_strtoll(const char *cp, char **endp, unsigned int base)  
  3. {  
  4.     if (*cp == '-')  
  5.         return -simple_strtoull(cp + 1, endp, base);  
  6.   
  7.     return simple_strtoull(cp, endp, base);  
  8. }  
  9. EXPORT_SYMBOL(simple_strtoll);  
    最后,strtoull调_parse_integer_fixup_radix和_parse_integer来处理相关逻辑:
  1. //simple_strtoull - convert a string to an unsigned long long   
  2. unsigned long long simple_strtoull(const char *cp, char **endp, unsigned int base)  
  3. {  
  4.     unsigned long long result;  
  5.     unsigned int rv;  
  6.   
  7.     cp = _parse_integer_fixup_radix(cp, &base);  
  8.     rv = _parse_integer(cp, base, &result);  
  9.     /* FIXME */  
  10.     cp += (rv & ~KSTRTOX_OVERFLOW);  
  11.   
  12.     if (endp)  
  13.         *endp = (char *)cp;  
  14.   
  15.     return result;  
  16. }  
  17. EXPORT_SYMBOL(simple_strtoull);  
    重头戏来了。接下来,我们来看上面strtoull函数中的parse_integer_fixup_radix和_parse_integer两段代码。如鲨鱼所说
  • “真正的处理逻辑主要是在_parse_integer里面,关于溢出的处理,_parse_integer处理的很优美,
  • 而_parse_integer_fixup_radix是用来自动根据字符串判断进制的”。
    先来看 _parse_integer函数:
  1. //lib/kstrtox.c, line 39     
  2. //Convert non-negative integer string representation in explicitly given radix to an integer.     
  3. //Return number of characters consumed maybe or-ed with overflow bit.     
  4. //If overflow occurs, result integer (incorrect) is still returned.     
  5. unsigned int _parse_integer(const char *s, unsigned int base, unsigned long long *p)    
  6. {    
  7.     unsigned long long res;    
  8.     unsigned int rv;    
  9.     int overflow;    
  10.     
  11.     res = 0;    
  12.     rv = 0;    
  13.     overflow = 0;    
  14.     while (*s) {    
  15.         unsigned int val;    
  16.     
  17.         if ('0' <= *s && *s <= '9')    
  18.             val = *s - '0';    
  19.         else if ('a' <= _tolower(*s) && _tolower(*s) <= 'f')    
  20.             val = _tolower(*s) - 'a' + 10;    
  21.         else    
  22.             break;    
  23.     
  24.         if (val >= base)    
  25.             break;    
  26.         /*  
  27.          * Check for overflow only if we are within range of  
  28.          * it in the max base we support (16)  
  29.          */    
  30.         if (unlikely(res & (~0ull << 60))) {    
  31.             if (res > div_u64(ULLONG_MAX - val, base))    
  32.                 overflow = 1;    
  33.         }    
  34.         res = res * base + val;    
  35.         rv++;    
  36.         s++;    
  37.     }    
  38.     *p = res;    
  39.     if (overflow)    
  40.         rv |= KSTRTOX_OVERFLOW;    
  41.     return rv;    
  42. }  
    解释下两个小细节:
  1. 上头出现了个unlikely,其实unlikely和likely经常出现在linux相关内核源码中
    1. if(likely(value)){  
    2.     //等价于if(likely(value)) == if(value)   
    3. }  
    4. else{  
    5. }  
    likely表示value为真的可能性更大,而unlikely表示value为假的可能性更大,这两个宏被定义成:
    1. //include/linux/compiler.h   
    2. # ifndef likely   
    3. #  define likely(x) (__builtin_constant_p(x) ? !!(x) : __branch_check__(x, 1))   
    4. # endif   
    5. # ifndef unlikely   
    6. #  define unlikely(x)   (__builtin_constant_p(x) ? !!(x) : __branch_check__(x, 0))   
    7. # endif  
  2. 呈现下div_u64的代码:
    1. //include/linux/math64.h   
    2. //div_u64   
    3. static inline u64 div_u64(u64 dividend, u32 divisor)  
    4. {  
    5.     u32 remainder;  
    6.     return div_u64_rem(dividend, divisor, &remainder);  
    7. }  
    8.   
    9. //div_u64_rem   
    10. static inline u64 div_u64_rem(u64 dividend, u32 divisor, u32 *remainder)  
    11. {  
    12.     *remainder = dividend % divisor;  
    13.     return dividend / divisor;  
    14. }  
    最后看下_parse_integer_fixup_radix函数:
  1. //lib/kstrtox.c, line 23   
  2. const char *_parse_integer_fixup_radix(const char *s, unsigned int *base)  
  3. {  
  4.     if (*base == 0) {  
  5.         if (s[0] == '0') {  
  6.             if (_tolower(s[1]) == 'x' && isxdigit(s[2]))  
  7.                 *base = 16;  
  8.             else  
  9.                 *base = 8;  
  10.         } else  
  11.             *base = 10;  
  12.     }  
  13.     if (*base == 16 && s[0] == '0' && _tolower(s[1]) == 'x')  
  14.         s += 2;  
  15.     return s;  
  16. }  
    读者MJN君在我的建议下,对上述linux内核中的atoi函数进行了测试,咱们来看下测试结果如何。
2147483647 : 2147483647
2147483648 : -2147483648
10522545459 : 1932610867
-2147483648 : -2147483648
-2147483649 : -2147483647
-10522545459 : 1932610867
    如上,根据程序的输出结果可以看出,对于某些溢出的情况,atoi程序的处理并不符合本题的要求
 也就是说,atoi程序对溢出的处理是一个标准,而本题要求对溢出的处理则是另外一个标准,所以说直接用atoi程序达不到本题的要求,但你不能因为本题的标准而否认atoi程序的正确性
  既然直接借用atoi的源码(原理是parseXXX,int i=Integer.parseInt(String str),把str转换成int的方法),不符合题目要求,则咱们另寻他路。
  路漫漫其修远兮,吾等将上下而求索,但与此同时,我们已渐入佳境。