C语言 检查循环中的uint64_t溢出

nqwrtyyt  于 2023-04-29  发布在  其他
关注(0)|答案(1)|浏览(197)

我有一个C方法,它计算n的collatz序列的第k个数。
如果n大于64位,则该方法可以返回0。
然而,我的方法有很多假阳性。如何更好地检查64位溢出?

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;    
}
qlzsbp2j

qlzsbp2j1#

你应该做两件事:
1.仅在计算3*n+1时应用溢出检查。
1.使用n > (UINT64_MAX - 1) / 3而不是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;    
}

如果你的乘法因子不是一个编译时常数(3),而是一个只在运行时才知道的东西,你可以使用here建议的其他溢出检查方法之一。

相关问题