check for uint64_t overflow in a loop

Question

I have a C-method which calculates the k-th number of the collatz-sequence of n.

If n is / gets bigger than 64-Bit the method may return 0.

My approach however has a lot of false positives. How can a check for an 64 Bit overflow better?

uint64_t collatz_K(uint64_t n, uint64_t k) {

    while (k>0){

        if(n > (UINT64_MAX / 3)-1){
           return 0;                   // check if overflow occurs.
        } if(n==1 && k%2==0){
           break;                      //premature break of the method if the end of the sequence is reached.
        }
        else{
            if(n%2 == 0){
                n = n >> 1;
            }else {
                n = 3*n +1;
            }                
            k--;
        }
    }
    return n;    
}

Answer 1

You should do two things:

1. Apply the check for overflow only in the case when you calculate 3*n+1.
2. Use n > (UINT64_MAX - 1) / 3 instead of n > (UINT64_MAX / 3) - 1.

uint64_t collatz_K(uint64_t n, uint64_t k) {
    for (; k>0; --k) {
        if (n==1 && k%2==0) {
           break; // premature break of the method if the end of the sequence is reached.
        }
        
        if(n%2 == 0){
            n = n >> 1;
        } else {
            if (n > (UINT64_MAX - 1) / 3)
                return 0; // Overflow will occur
            
            n = 3*n + 1;
        }                
    }
    return n;    
}

If your multiplication factor wasn't a compile-time constant (3) but something known only in runtime, you could have used one of the other overflow check approaches suggested here.