检测 C 函数中的无符号整数溢出

Detecting a unsigned integer overflow in a c function

当 n 大于 64 位时如何检测函数溢出?

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

您可以检测溢出,或者更准确地说,通过将值与操作前计算出的最大值进行比较来检测环绕:

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

表达式 n /= 2; 永远不会溢出,所以我不担心。

我想你问的问题是:

n = (3 * n) + 1; 会溢出吗?

可以回答为不等式:

  • 如果(3 * n) + 1 > UINT64_MAX,那么你有溢出。

这是一个可以用代数求解的不等式。

  • 如果(3*n) > UINT64_MAX-1,那么你有溢出
  • 如果n > (UINT64_MAX-1)/3,那么你有溢出

所以,最终,如果n > (UINT64_MAX-1)/3(或大约6.1489e18),那么你无法在不溢出uint64_t的情况下完成计算。