I am converting a number string to a number using the old x = x * 10 (c - '0') method, char by char. I know about atoi, strtol, etc...

The problem is that I want to make sure that x will never exceed the maximum possible value the type can handle. But I do want to also support arbitrary max values that are less than e.g. UINT_MAX, but still if you add 1 more char, it would overflow.

The only solution I came up with is to either make x one type greater than the maximum one I want to support, but that doesn't sound good.

Also, since this is not your usual addition, there is more math involved, and testing if UINT_MAX / 10 > (double) (x (c - '0') / 10) seems wrong.

I am inexperienced with this and I'm hoping for some cool math or bitshift trick to make sure that appending the number c to number x won't be greater than max (which will usually be the maximum allowable type size like UINT_MAX or ULONG_MAX, etc...)

#include <stdio.h>
#include <limits.h>

int main() {
    max = UINT_MAX;
    unsigned int x;
    char *str = "65536";
    int i;

    for (i = 0; str[i] != '\0', i  ) {
        if (/* ??? test if adding new digit will exceed max ??? */) {
            x = x * 10   (str[i] - '0');
        }
        else
            break;
    } 

    printf("x = %ud\n", x);

    return 0;
}

Thank you!

CodePudding user response：

//  Will multiplying x by 10 and adding digit d overflow "unsigned int"?
_Bool WillItOverflow(unsigned int x, unsigned int d)
{
    if (x > UINT_MAX/10)
        return 1;
    else if (x == UINT_MAX/10 && d > UINT_MAX - UINT_MAX/10*10)
        return 1;
    else
        return 0;
}

A proof follows. Text in code style is the value of code (e.g., 37/10 is 3); other mathematical operations are ordinary real arithmetic (37/10 is 3.7).

• Since integer division truncates, UINT_MAX/10 = (UINT_MAX− r)/10, where r is the remainder of UINT_MAX modulo 10. Necessarily, r < 10, and note that r = UINT_MAX - UINT_MAX/10*10.
• If x > UINT_MAX/10, x >= UINT_MAX/10 1 = (UINT_MAX−r)/10 1, so 10•x >= UINT_MAX-r 10, so 10•x >= UINT_MAX 1.
• If x = UINT_MAX/10, 10•x d = 10•((UINT_MAX−r)/10) d = UINT_MAX−r d, which clearly is greater than UINT_MAX if and only iff d > r.
• Otherwise, x < UINT_MAX/10, so x ≤ UINT_MAX/10−1, so 10•x d ≤ 10•((UINT_MAX−r)/10)−10 d = UINT_MAX−r−10 d, and −r−10 d is non-positive since d < 10, so 10•x d ≤ UINT_MAX.

CodePudding user response：

If you use gcc compiler you can use builtin functions:

 int main() {
    unsigned int x = 0, tmp, tmp2;
    char *str = "4294967296";
    while(*str)
    {
        if(!__builtin_umul_overflow (x, 10, &tmp) && !__builtin_uadd_overflow(tmp, *str   - '0', &tmp2)) 
        {
            x = tmp2;
        }
        else
            break;
    } 
    printf("x = %u\n", x);
}

Those functions compile the the very efficient assembly code: https://godbolt.org/z/xM1959bcd

CodePudding user response：

There is no standard way to detect integer overflow after it happens, but you can perform simple math to detect it before trying to add the next digit:

#include <limits.h>
#include <stdio.h>

int main() {
    unsigned int x = 0;
    const char *str = "655360000000";
    int i;
    char cc;

    for (i = 0; (cc = str[i]) >= '0' && cc <= '9'; i  ) {
        if (x < UINT_MAX / 10
        ||  (x == UINT_MAX / 10 && cc - '0' <= UINT_MAX % 10)) {
            x = x * 10   (cc - '0');
        } else {
            /* number is too large */
            x = UINT_MAX;
            break;
        }
    } 
    printf("x = %u\n", x);
    return 0;
}

This method works for all integer types.

Note however that unsigned types do not overflow, the arithmetics on unsigned types are defined modulo the maximum value plus one. So you could use a simpler sloppy method (albeit not recommended):

#include <limits.h>
#include <stdio.h>

int main() {
    unsigned int x = 0;
    const char *str = "655360000000";
    int i;
    char cc;

    for (i = 0; (cc = str[i]) >= '0' && cc <= '9'; i  ) {
        unsigned int x0 = x;
        x = x * 10   (cc - '0');
        if (x < x0) {
            /* number is too large */
            x = UINT_MAX;
            break;
        }
    }
    printf("x = %u\n", x);
    return 0;
}