String to Integer: atoi()

From Software Engineers Wiki
Jump to: navigation, search

Convert a string to an integer.

Answer #1. Without overflow detection

int atoi(const char *str)
{
        int value = 0;
        int negative = 0;
        const char *cp;

        /* skip white space */
        for (cp = str; isspace(*cp); ++cp)
                ;

        /* sign */
        if (*cp == '+') {
                ++cp;
        } else if (*cp == '-') {
                negative = 1;
                ++cp;
        }

        /* number */
        while (isdigit(*cp)) {
                value = value * 10 + (*cp - '0');
                ++cp;
        }

        return (negative) ? -value : value;
}

Answer #2. With overflow detection

For latest gcc, there are builtin functions __builtin_sadd_overflow(). It can check the overflow flag in the microprocessor to detect the overflow easily. Without this type of functions, the C code can't detect overflow flag, and needs to perform some arithmetic to check the overflow.

In following example, the atoi() returns INT_MAX or INT_MIN if overflows or underflows.

int mul_overflow(unsigned int value, unsigned int opnd, int negative, unsigned int *result)
{
        unsigned int new_value;
        unsigned int int_max = (negative) ? ((unsigned) INT_MAX + 1) : (INT_MAX);

        new_value = value * opnd;

        if (new_value > int_max)
                return 1;
        if (new_value / opnd != value)
                return 1;

        *result = new_value;

        return 0;
}

int add_overflow(unsigned int value, unsigned int opnd, int negative, unsigned int *result)
{
        unsigned int new_value;
        unsigned int int_max = (negative) ? ((unsigned) INT_MAX + 1) : (INT_MAX);

        new_value = value + opnd;

        if (new_value > int_max)
                return 1;

        *result = new_value;

        return 0;
}

int atoi(const char *str)
{
        unsigned int value = 0;
        int negative = 0;
        const char *cp;
        int overflow = 0;

        /* skip white space */
        for (cp = str; isspace(*cp); ++cp)
                ;

        /* sign */
        if (*cp == '+') {
                ++cp;
        } else if (*cp == '-') {
                negative = 1;
                ++cp;
        }

        /* number */
        while (isdigit(*cp)) {
                /* value = value * 10 + (*cp - '0'); */
                overflow = mul_overflow(value, 10, negative, &value);
                if (!overflow)
                        overflow = add_overflow(value, *cp - '0', negative, &value);
                if (overflow)
                        break;
                ++cp;
        }

        if (overflow)
                return (negative) ? INT_MIN : INT_MAX;

        return (negative) ? (int) -value : (int) value;
}
Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox