Detecting a unsigned integer overflow in a c function-CodePudding

How to detect overflow in a function when n becomes greater than 64 bits?

uint64_t col(uint64_t n) 
{
    int count = 0;

    while (n != 1) {
        if (n % 2 == 0) {
            n /= 2;
        } else {
            n = (3 * n)   1;
        }
        count  ;
    }
    return count;
}

CodePudding user response：

You can detect overflow, or more precisely wrap around, by comparing the value with a computed maximum before the operation:

#include <stdio.h>
#include <stdint.h>

uint64_t collatz(uint64_t n) {
    uint64_t count = 0;

    if (n == 0) {
        return count;
    }

    while (n != 1) {
        if (n % 2 == 0) {
            n /= 2;
        } else {
            if (n > (UINT64_MAX - 1) / 3) {
                printf("overflow!\n");
                return UINT64_MAX;
            }
            n = (3 * n)   1;
        }
        if (count == UINT64_MAX) {
            printf("too many iterations!\n");
            return UINT64_MAX;
        }
        count  ;
    }
    return count;
}

CodePudding user response：

The expression n /= 2; should never overflow, so I'm not worried about that.

The question I think you're asking is:

Will n = (3 * n) 1; ever overflow?

That can be answered as an inequality:

If (3 * n) 1 > UINT64_MAX, then you have Overflow.

And that is an inequality you can solve algebraically.

If (3*n) > UINT64_MAX-1, then you have Overflow
If n > (UINT64_MAX-1)/3, then you have Overflow

So, ultimately, if n > (UINT64_MAX-1)/3 (or approximately 6.1489e18), then you cannot complete the calculation without overflowing uint64_t.