leetcode8.StringtoInteger(atoi)&探讨补码运算溢出

题意：实现atoi函数，各种细节如下

1. 字串为空或者全是空格，返回0； 

2. 字串的前缀空格需要忽略掉；

3. 忽略掉前缀空格后，遇到的第一个字符，如果是‘+’或‘－’号，继续往后读；如果是数字，则开始处理数字；如果不是前面的2种，返回0；

4. 处理数字的过程中，如果之后的字符非数字，就停止转换，返回当前值；

5. 在上述处理过程中，如果转换出的值超出了int型的范围，就返回int的最大值或最小值。

关键点：如何判断溢出，关于有符号数加法，乘法的溢出判断

class Solution {
public:
    int myAtoi(string str) {
int len = str.length();
int i = 0;
//i指向第一个非空字符
while(str[i]==' ' && i//全是空格,则返回零
if (i==len) return 0;
//符号位
int sign = 1;
if (str[i]=='-') sign = -1;
int res = 0;
//数字带有正负号
if(str[i]=='-'||str[i]=='+'){
i++;
}
//以数字开头
if(str[i]>='0' && str[i]<='9'){
while(iif (str[i]>='0' && str[i]<='9'){
if (res>(INT_MAX-(str[i]-'0'))/10)//溢出了
return (sign == 1)?INT_MAX:INT_MIN;
else
res = res*10+(str[i]-'0');
}
else
return (sign == 1)?res:-1*res;
i ++;
}
return (sign == 1)?res:-1*res;
}
//不以'+','-',数字开头,则返回0 
        return 0;
    }
};

判断溢出的正确写法：

if (res>(INT_MAX-(str[i]-'0'))/10)//溢出了

错误写法1

if (res<0)//溢出了    return (sign == 1)?INT_MAX:INT_MIN;

说明：只有x+y，也即补码加法，才能通过符号位来判断是否溢出，对于x+y，如果x,y很大时，就会得出负值。但是对于补码乘法，没有这个性质。

说明：x,y都是w位的，s=x*y,s可能需要不止(w+1)来表示。

错误写法2：

if (res*10+（str[i]-'0'）>INT_MAX)//溢出了
return (sign == 1)?INT_MAX:INT_MIN;

说明：res*10本身已经溢出了，所以，即使res*10+(str[i]-'0')的真实值大于INT_MAX，但是其溢出值不一定大于INT_MAX.