循环检查 uint64_t 溢出

Question

我有一个 C 方法，它计算

k

的 collatz 序列的第

n

个数。

如果 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;    
}

Answer 1

首先，请注意，只有在计算

3*n+1

的情况下才需要检查溢出。

其次，您可以采用以下两种方法之一：

1. 如果您使用

   gcc

   或

   clang

   构建并且没有严格的 C 标准合规性要求，则可以利用编译器的 Integer Overflow Builtins。基本上，这些检查指示溢出的 CPU 进位位。根据我的口味，这是最优雅和最高效的方式：

   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 {
               // n = 3*n +1;
   
               uint64_t res;
               if (__builtin_umull_overflow(3, n, &res) || res == UINT64_MAX)
                   return 0; // Overflow occurred
   
               n = res + 1;
           }                
       }
       return n;    
   }
   

   神箭

2. 如果您确实有严格的 C 标准合规要求。您可以使用 here 中讨论的其他方法之一。例如检查 x / a != b

   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 {
               uint64_t res = 3*n + 1;
               if ((res - 1) / 3 != n)
                   return 0; // Overflow occurred
   
               n = res;
           }                
       }
       return n;    
   }