C语言 使用 gcc c99 编译，而不是使用 ideone c99.整数溢出

Question

int rng(int min, int max){
    int result = min + ( ( (max - (min - 1) ) * rand() ) / (RAND_MAX + 1) );
    return result;
}

这不会使用 c99 模式使用 ideone 进行编译，但是当我在 -std=c99 上在代码块上使用 gcc 时会这样做。我认为使用 long int 可以解决问题，但显然并非如此。当我在学校尝试一些东西时，我会使用 ideone，因为他们只有 VC++，而我正在做 C C99。我不想在需要时不使用此功能，因此在这里我询问出了什么问题。

Answer 1

实际上，在我的编译器上，这会产生warning: integer overflow in expression [-Woverflow].

该问题是由RAND_MAX + 1引起的。 RAND_MAX经常碰巧与INT_MAX相同。当然，将1添加到INT_MAX会产生未定义的行为(除了编译器在编译时捕获并用其他内容替换代码(。

如果你想在行动中看看为什么它不好，请这样做：

scanf("%d", &dummy); /* So the compiler won't catch it. */
dummy += INT_MAX;
gcc -ftrapv -Wall -Wextra # ftrapv is the key point

Answer 2

在 ideone 中查看一下。

#include <stdlib.h>
#include <stdio.h>
int main(void) { printf("%xn", RAND_MAX); return 0; }

您会注意到它打印7fffffff，这可能也是MAX_INT。 计算MAX_INT + 1时会发生什么？ 计算MAX_INT + 1是错误的，无论你是否收到错误。

有很多方法可以编写具有不同范围的统一 RNG 的统一随机数生成器，但正确执行此操作有点棘手。

这应该在max - min <= RAND_MAX和max > min时起作用......

int rng(int min, int max)
{
    int range = max - min + 1;
    int factor = ((unsigned) RAND_MAX + 1) / range;
    int x;
    do {
        x = rand() / factor;
    } while (x >= range);
    return x + min;
}

这应该是统一的，并且给出相对高质量的数字(使用%已知会导致某些 PRNG 和某些范围出现严重的质量问题(。

Answer 3

没有实际的错误文本，很难说，但是标题中"整数溢出"的存在指向......，嗯，整数溢出：-(

最有可能的罪魁祸首是你的RAND_MAX +1位，如果RAND_MAX实际上与INT_MAX相同.

如果你愿意放弃随机数^{的完美分布(a(，}你可以选择如下：

int rng (int minVal, int maxVal) {
    int result = min + (rand() % (maxVal + 1 - minVal));
    return result;
}

---

^(a( 这样做造成的"损害"通常很小，但确实使分布略微偏离最高值。如果这很重要，还有其他方法，但对于统计学家以外的大多数人来说，损害是可以接受的。

Answer 4

这确实会产生整数溢出，如果(max - min + 1) * RAND_MAX > INT_MAX . 关于如何避免这种情况，您有几个选择：

• 将中间值强制转换为可以存储它们而不会溢出的类型，例如 uint64_t 或 double ，或
• 请改用模运算符%，如下所示：

int rng ( int min, int max ) {
    return min + rand() % (max - min + 1);
}

请注意，使用 % 有一些缺点：如果 max - min + 1 不是 2 的幂，它会稍微将结果偏向范围的低端(因为它不会均匀地除RAND_MAX+1(;如果是 2 的幂，它可能会降低随机数流的周期和质量(因为 LCRNG 的低位比高位的随机性小(。

有一些方法可以通过仔细编码来避免这些问题。 例如，请参阅 Java 中的标准Random.nextInt()实现，它可以非常简单地转换为 C：

int rng (int min, int max) {
    int n = max - min + 1;
    int bits, val;
    if ((n & -n) == n)  // i.e., n is a power of 2
        return min + (int)((n * (uint64_t)rand()) / ((uint64_t)RAND_MAX + 1));
    do {
        bits = rand();
        val = bits % n;
    } while(bits - val > RAND_MAX - (n-1));
    return min + val;
}

(我认为这个翻译应该按预期工作。 结果比我有点棘手，因为原始的Java代码实际上依赖于INT_MAX = RAND_MAX = (1<<31)-1的假设，这在C中可能不成立。