1

我被迫将输出存储在一个unsigned int数组中。但是，输出是数组中先前元素的线性组合的解，以2147483647 为模，即以2^31-1 为模。

下面是一个更大函数的代码片段。很快，这个片段会产生错误ii的答案，因为它会围绕xx. （请注意，xx在调用函数之前播种，因此数组中没有元素为空。）

#include <stdint.h>
typedef unsigned int uint32;
typedef unit_least64_t uint64;
static uint32 xx[47];

...

xx[ii] = 12345 * (uint64)(xx[i0] + xx[ii]) % 2147483647;  // i0, ii are defined elsewhere

但是，如果我们将最后一行与以下内容交换，我们将不断得到正确的解决方案。

xx[ii] = 12345 * ( (uint64)xx[i0] + (uint64)xx[ii] ) % 2147483647;

也许，这很明显，但是为什么需要对 unit64 进行两次类型转换而不是一次呢？

4

2 回答 2

1

只要你把它放在正确的地方，一种类型的演员就足够了：

xx[ii] = 12345 * ( (uint64)xx[i0] + xx[ii] ) % 2147483647;

重要的是在加法之前进行强制转换以防止数字溢出，而不是在溢出已经发生时。

于 2013-10-16T02:59:02.800 回答
1

是的，您的初始代码可以这样编写：

uint32 t1 = xx[i0] + xx[ii]; // problem is here, result of sum is truncated as it is 32 bit
uint64 t2 = (uint64)t1;
uint64 t3 = 12345 * t2 % 2147483647;
xx[ii] = (uint32)t3;

如果您使用第二种变体，您将拥有：

uint64 t0 = (uint64)xx[i0];
uint64 t1 = (uint64)xx[ii];
uint64 t2 = t0 + t1; // no truncation, as the result is 64 bit
uint64 t3 = 12345 * t2 % 2147483647;
xx[ii] = (uint32)t3;
于 2013-10-16T02:59:06.453 回答