为什么对于整数来说，x = x * y / z和x *= y / z会得到不同的结果？

Question

我有以下函数:

pub fn s_v1(n: &u64) -> u64 {
    let mut x: u64 = 1;

    for i in 1..=*n  {
        x = x * (*n + i) / i;
    }

    x
}

这段代码可以正确得出 s_v1(&20) == 137846528820 的答案。

然而，如果我将 for 循环中的行改为 x *= (*n + i) / i;，则答案会变成 s_v1(&20) == 16094453760。

为什么结果不同？x = x * y 和 x *= y 不是一样的吗？

- Aditeya

---

x = x * y 和 x *= y 的意思相同，但是你的表达式不是这种形式。其中有一个除法运算。x = x * y / z 不等同于 x *= y / z。因为运算顺序不同。 - n. m.

如果/表示整数除法，那么a * (b / c)和(a * b) / c之间存在区别，因为余数舍去的方式不同。 - qrsngky

@qrsngky: 是的，所有涉及的3个变量都是“u64”类型，因此这是整数除法。（函数参数以参考方式为“u64”，没有明显的原因或优势，所以“*n”会解引用它以获取“u64”。） - Peter Cordes

你可以安全地将 x = x * (*n + i) / i; 更改为 x *= (*n + i); x /= i;。 - Ben Voigt

请注意，该函数似乎在计算nCr(2*n,n)，即从一个大小为2n的集合中（不重复地）抽取n个元素的无序组合数。 - Ben Voigt

Answer 1

由于 * 和 / 具有相同的优先级和左结合性，因此该表达式不是

x * ((*n + i) / i)

这与 x *= (*n + i) / i 相同，但

(x * (*n + i)) / i

- Chayim Friedman

---

在精确算术中，这两个东西是相同的，因此根本原因不仅仅是优先级，而是整数算术。 - Pablo H

Answer 2

如其他人所指出的，有两个因素导致了这个问题：

1. a*=b/c 等同于 a=a*(b/c) 而不是 a=a*b/c（这隐含着 a=(a*b)/c）。

2. / 根据操作数的类型进行除法运算。在这种情况下，操作数都是整数，因此 / 表示整数除法，舍弃余数。因此，(a*b)/c 不等同于 a*(b/c)（除非 b 是 c 的倍数）。

如果你想要替换循环中的那一行，你需要将这两个操作分开执行。

    for i in 1..=*n  {
        x *= *n + i;
        x /= i;
    }

这个算法的一个缺点是当答案应该在MAXINT/2n和MAXINT之间时，它将无法产生正确的结果。为了解决这个问题，你实际上需要利用你原本尝试做的事情：

    for i in 1..=*n  {
        if (x % i == 0) {
            x /= i;
            x *= *n + i;
        } else if (*n % i == 0) {
            x *= *n / i + 1;
        } else {
            x *= *n + i;
            x /= i;
        }
    }

- Martin Kealey