3

我在 TopCoder 中编写了一个问题。在一个计算步骤中，可能会出现溢出，分析表明解决方案的时间过长。我不明白为什么这会起作用。 

int normalize(int pos) {
    return (int) (((long) pos % MODULO + MODULO) % MODULO);
}

变量pos和MODULO都可能来自范围 -2147483648 和 2147483647
我想知道转换为 long 有什么帮助？谢谢！

4

2 回答 2

2

我认为如果您稍微重构代码并将每个表达式都放在自己的行中，它会变得更加清晰。

varpos和MODULO都可以在 -2147483648 和 2147483647 范围内

请注意，准确地说：Integer.MAX_VALUE== 2147483647。以边缘情况（pos并且MODULO尽可能大）是一个很好的例子：

public static void main(String[] args) {
    System.out.println("result: "
            + normalize(Integer.MAX_VALUE-1, Integer.MAX_VALUE));
    System.out.println();
    System.out.println("result: "
            + normalizeWithoutLongCast(Integer.MAX_VALUE-1, Integer.MAX_VALUE));
}

static int normalize(int pos, int MODULO) {
    System.out.println("normalize()");
    long mod = pos % MODULO;
    System.out.println("mod: "+mod);
    long sum = mod + MODULO; // this is where the overflow can occur
    System.out.println("sum: "+sum);
    return (int) (sum % MODULO);
}

static int normalizeWithoutLongCast(int pos, int MODULO) {
    System.out.println("normalizeWithoutLongCast()");
    int mod = pos % MODULO;
    System.out.println("mod: "+mod);
    int sum = mod + MODULO; // this is where the overflow can occur
    System.out.println("sum: "+sum);
    return (int) (sum % MODULO);
}

输出：

normalize()
mod: 2147483646
sum: 4294967293
result: 2147483646

normalizeWithoutLongCast()
mod: 2147483646
sum: -3
result: -3

因此，如您所见，问题恰好发生在sum = mod + MODULO;步骤中。

就像MODULO差不多一样Integer.MAX_VALUE，这意味着添加尽可能少1的值会返回一个大于整数的值（整数溢出）。

因为，在 ( mod = pos2 % MODULO) 之前的步骤中，你有 that modcan be 1，可能会发生溢出。

转换为long将允许总和发生而不必担心溢出。当然，如果我们希望结果是int.

幸运的是，这不是问题，因为最后一个表达式的值 ( sum % MODULO) 在0and之间MODULO。并且MODULO最多可以Integer.MAX_VALUE( 2147483647) 它是一个有效的整数，因此可以安全地转换回int.

于 2013-08-13T03:23:43.230 回答
2

在 Java 中，longs 始终是 64 位的量。当用两个不同宽度的量执行算术时，Java 的规范说算术是用更大的数据类型完成的。

因此，通过转换pos为 a long，所有后续算术都使用 64 位longs 完成。由于最后一步是对 32 位值进行 mod，因此结果肯定可以适合 32 位，因此最终转换不会丢失精度。

于 2013-08-13T03:17:30.180 回答