The expression of detection with the unsigned integer overflow

Question

The program will generate factorial number until it occurs overflow. The expression r <= UINT_MAX / j is to detect the overflow. For now, if I rewrite the expression to this r * j <= UINT_MAX, it will enter the infinite loop. My question is NOT about how to detect the integer overflow. That is why the expression will let the process enter the infinite loop.

for (unsigned i = 0;;++i) {
    unsigned r = 1;
    for (unsigned j = 2; j <= i; ++j) {
        if (r <= UINT_MAX / j) 
            r *= j;
        else {
            printf("Overflow!\n");
        }
    }
}

The expression `r * j` is also an unsigned int. So it can never be larger than `UINT_MAX`. — wimh, Aug 22 '15 at 08:20
possible duplicate of [Test for overflow in integer addition](http://stackoverflow.com/questions/3422709/test-for-overflow-in-integer-addition) — wimh, Aug 22 '15 at 08:24
possible duplicate of [How to detect integer overflow in C/C++?](http://stackoverflow.com/questions/199333/how-to-detect-integer-overflow-in-c-c) — phuclv, Aug 22 '15 at 09:15

pablo1977 · Accepted Answer · 2015-08-22T08:56:44.427

Unsigned integer types have arithmetic modulo its maximum value plus 1.
In your case, we have arithmetic modulo (UINT_MAX+1).

So, the operation r*j always gives a result <= UINT_MAX, and the comparison is always true.

However, when r is compared against UINT_MAX / j, the real (mathematical) arithmetic coincides with the unsigned type arithmetic, because UINT_MAX / j is mathematically in the range of unsigned.
This explains why in the C-code the condition would be true or false exactly the same way as the mathematical comparison is.

Thus, the r <= UINT_MAX/j approach is the correct one.

The expression of detection with the unsigned integer overflow

1 Answers1