atoi和itoa函数及负数转正数时溢出问题


首先贴出c函数库里的atoi函数, 其实是atol函数, 因为atoi调用了atol函数. 函数很简单,相信大家一看就懂.

其中isspace函数是判断传入字符是否为空白符, 空白符指空格, 水平制表, 垂直制表, 换页, 回车和换行符.

函数首先跳过空白字符, 之后判断正负号, 判断完正负号后判断字符是否为数字, 如果是则循环, 直到遇到非数字为止, 如果第一次循环就不是数字则直接返回 total ,此时 total为 0.

atoi函数:
/***
*long atol(char *nptr) - Convert string to long
*
*Purpose:
*       Converts ASCII string pointed to by nptr to binary.
*       Overflow is not detected.
*
*Entry:
*       nptr = ptr to string to convert
*
*Exit:
*       return long int value of the string
*
*Exceptions:
*       None - overflow is not detected.
*
*******************************************************************************/

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 */
}


/***
*int atoi(char *nptr) - Convert string to long
*
*Purpose:
*       Converts ASCII string pointed to by nptr to binary.
*       Overflow is not detected.  Because of this, we can just use
*       atol().
*
*Entry:
*       nptr = ptr to string to convert
*
*Exit:
*       return int value of the string
*
*Exceptions:
*       None - overflow is not detected.
*
*******************************************************************************/

int __cdecl atoi(
        const char *nptr
        )
{
        return (int)atol(nptr);
}


关于itoa函数, 我会贴出三个版本, 第一个是网上找的, 第二个是c函数库里的, 第三个我自己写的(利用“c陷阱和缺陷”里的一段代码改的).

版本1:
char * my_itoa( int num, char*str, int radix )
{
    const char table[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" ;
    char*ptr=str ;
    bool negative=false ;
    if(num==0)
    {
        //num=0
        *ptr++='0' ;
        *ptr='/0' ;
        // don`t forget the end of the string is '/0'!!!!!!!!!
        return str ;
    }
    if(num<0)
    {
        //if num is negative ,the add '-'and change num to positive
        *ptr++='-' ;
        num*=-1 ;
        negative=true ;
    }
    while(num)
    {
        *ptr++=table[num%radix];
        num/=radix ;
    }
    *ptr='/0' ;
    //if num is negative ,the add '-'and change num to positive
    // in the below, we have to converse the string
    char*start=(negative?str+1:str);
    //now start points the head of the string
    ptr--;
    //now prt points the end of the string
    while(start<ptr)
    {
        char temp=*start ;
        *start=*ptr ;
        *ptr=temp ;
        start++;
        ptr--;
    }
    return str ;
}


其实, 这个版本的itoa函数有个很明显的错误, 相信看过"c陷阱和缺陷" 的朋友已经看出来了, 那就是溢出的问题, 代码中有这么一句话 num* = -1,这句话是在num为负数时将num转化为正数, 但问题是计算机存储整数用的是补码形式, 这就导致负数的表示范围比正数大一点. 我们以 int 占4字节为例, 其中负数最小可以为 -2^31 = -2147483648. 而正数最大为 2^31-1 = 2147483647. 所以如果不幸的是我们传入函数的num是负数,并且是最小的负数,那么程序就会出问题了. 比如说如果num = -2147483648, 那么num*=-1,之后num的值还是为-2147483648, 没有变化, 大家可以查看汇编imul之后的结果. 这就导致之后求得的索引是乱码. 所以最后输出的字符串也是乱码. 那如何修改程序呢, 其实很简单,我们再定义一个unsigned int num_neagtive; 将num*=-1; 这句话换成 num_negative = (unsigned int )(-num_negative); , 并且将之后的num换成num_negative就好了.

版本2:
static void __cdecl xtoa (
        unsigned long val,
        char *buf,
        unsigned radix,
        int is_neg
        )
{
        char *p;                /* pointer to traverse string */
        char *firstdig;         /* pointer to first digit */
        char temp;              /* temp char */
        unsigned digval;        /* value of digit */

        p = buf;

        if (is_neg) {
            /* negative, so output '-' and negate */
            *p++ = '-';
            val = (unsigned long)(-(long)val);
        }

        firstdig = p;           /* save pointer to first digit */

        do {
            digval = (unsigned) (val % radix);
            val /= radix;       /* get next digit */

            /* convert to ascii and store */
            if (digval > 9)
                *p++ = (char) (digval - 10 + 'a');  /* a letter */
            else
                *p++ = (char) (digval + '0');       /* a digit */
        } while (val > 0);

        /* We now have the digit of the number in the buffer, but in reverse
           order.  Thus we reverse them now. */

        *p-- = '\0';            /* terminate string; p points to last digit */

        do {
            temp = *p;
            *p = *firstdig;
            *firstdig = temp;   /* swap *p and *firstdig */
            --p;
            ++firstdig;         /* advance to next two digits */
        } while (firstdig < p); /* repeat until halfway */
}

/* Actual functions just call conversion helper with neg flag set correctly,
   and return pointer to buffer. */

char * __cdecl _itoa (
        int val,
        char *buf,
        int radix
        )
{
        if (radix == 10 && val < 0)
            xtoa((unsigned long)val, buf, radix, 1);
        else
            xtoa((unsigned long)(unsigned int)val, buf, radix, 0);
        return buf;
}


版本3:
char * itoa_modified( int    val,
                      char  *buf,
                      int    radix )
{
    char *p, *firstdig;
    char temp;              /* temp char */

    p = buf;
    if ( val < 0 ) {
        *p++ = '-';
    }
    if ( val > 0 ) {
        val = -val;
    }
    firstdig = p;
    do {
        *p++ = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[-( val % radix )];
        val = val / radix;
    } while ( val );
    *p-- = '\0';
    do {
        temp = *p;
        *p = *firstdig;
        *firstdig = temp; /* swap *p and *firstdig */
        --p;
        ++firstdig; /* advance to next two digits */
    } while ( firstdig < p ); /* repeat until halfway */
    return ( buf );
}

这里如果val是正数则将它转换为负数, 之后统一按负数处理. 这样就不会出现溢出问题了.

0 个评论

要回复文章请先登录注册

收藏七月在线,一起向大牛进阶

ctrl+D或command+D可以快速收藏哦~