2

以下是从一个开源项目的 rand() 复制的，它使用 LCG

rand_next = rand_next * 1103515245L + 12345L;  //unsigned long rand_next

经典的LCG是：

下一个 = (下一个 * a + c) mod M

显然，这里的 M 是 2^32。

让我感到困惑的是 rand_next * 1103515245L，我很确定会发生溢出！我看一下几个 rand() 实现，除了使用不同的 a 和 c 外，都采用这种方式。

溢出有害吗？如果不是为什么？

谢谢

4

2 回答 2

3

这可以。根据 C99 规范，对于 unsigned long 操作，结果是相同的，但减少了模 2 32 (§6.2.5)：

A computation involving unsigned operands can never overflow, because a result 
that cannot be represented by the resulting unsigned integer type is reduced 
modulo the number that is one greater than the largest value that can be 
represented by the resulting type.

所以这种行为实际上并不是“溢出”，但为了简单起见，我将在这个答案中称之为。因为对于模算术，我们有

a1 ≡ b1 (mod m)
a2 ≡ b2 (mod m)

暗示

a1 + a2 ≡ b1 + b2 (mod m)

我们有

Next * a ≡ k (mod 2^32)

k“溢出”在哪里Next * a。所以自从M = 2^32,

Next * a + c ≡ k + c (mod M)

有“溢出”的结果在模运算下等价于没有“溢出”的结果，所以公式没问题。一旦我们减少模M = 2^32，它会给出相同的结果。

于 2013-06-21T02:58:47.017 回答
1

signed long你将 a与a 相乘unsigned long。因此， 的两个操作数*具有相同的整数转换等级。在这种情况下，以下规则（C++11, §5/9, item 5, sub-item 3）适用：

[...] 如果具有无符号整数类型的操作数的等级大于或等于另一个操作数类型的等级，则具有符号整数类型的操作数应转换为具有无符号整数类型的操作数的类型。

unsigned long因此，在计算乘法之前，两个操作数都被隐式转换为。因此，您得到无符号算术和无符号结果，并且相同的规则再次适用于加法运算。

unsigned 的整数溢出是明确定义的（参见Zongzhen Li's answer，刚刚扩展以详细介绍这一点），所以没有问题。

关于 C（相对于 C++），C11 在 §6.3.1.8/1 中有一个相同的规则：

[...]如果具有无符号整数类型的操作数的等级大于或等于另一个操作数类型的等级，则具有符号整数类型的操作数将转换为具有无符号整数类型的操作数的类型。

于 2013-06-21T03:09:15.640 回答