我有一个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;
}
1条答案
按热度按时间qlzsbp2j1#
你应该做两件事:
1.仅在计算
3*n+1
时应用溢出检查。1.使用
n > (UINT64_MAX - 1) / 3
而不是n > (UINT64_MAX / 3) - 1
。如果你的乘法因子不是一个编译时常数(3),而是一个只在运行时才知道的东西,你可以使用here建议的其他溢出检查方法之一。