在C#整数运算中,a / b / c总是等于a /(b * c)?

令a,b和c为非大正整数。 用C#整数运算,a / b / c总是等于a /(b * c)吗? 对我来说,在C#中看起来像:

int a = 5126, b = 76, c = 14; int x1 = a / b / c; int x2 = a / (b * c); 

所以我的问题是:所有的a,b和c的x1 == x2

\表示整数除法(两个int s之间的C# /运算符)并让/表示通常的math除法。 那么,如果x,y,z正整数 ,我们忽略溢出

 (x \ y) \ z = floor(floor(x / y) / z) [1] = floor((x / y) / z) [2] = floor(x / (y * z)) = x \ (y * z) 

哪里

 a \ b = floor(a / b) 

从上述行[1]到行[2]的跳转说明如下。 假设你有两个整数ab和一个在[0, 1)范围内的分数f 。 这是直截了当的看到这一点

 floor(a / b) = floor((a + f) / b) [3] 

如果在行[1]确定a = floor(x / y)f = (x / y) - floor(x / y)b = z ,则[3]意味着[1][2]是平等的。

你可以将这个certificate推广到负整数(仍然忽略溢出 ),但是我会留给读者来保持简单。


关于溢出问题 – 请参阅Eric Lippert的解答! 他还在博客文章和回答中采取了更为严格的方法,如果您觉得自己太过于手工,应该考虑一下。

我非常喜欢这个问题,于2013年6月4日成为我博客的主题。 感谢您的好问题!


大案件很容易来。 例如:

 a = 1073741823; b = 134217727; c = 134217727; 

因为b * c溢出到一个负数。

我会补充一点,在检查算术中a / (b * c)(a / b) / c之间的差异可以是工作的程序和崩溃的程序之间的差异。 如果bc的乘积溢出了整数的范围,那么前者将在检查的上下文中崩溃。

对于小的正整数,比如说小到可以放入空格中,就应该保持身份。


蒂莫西·希尔斯只是张贴了一个certificate 我在这里提出一个替代的certificate。 假设这里所有的数字都是非负整数,并且没有任何操作溢出。

x / y整数除法find值q ,使得q * y + r == x ,其中0 <= r < y

所以划分a / (b * c)find值q1

 q1 * b * c + r1 == a 

其中0 <= r1 < b * c

( a / b ) / c首先find这样的值qt

 qt * b + r3 == a 

然后find这样的值q2

 q2 * c + r2 == qt 

所以用qt代替,我们得到:

 q2 * b * c + b * r2 + r3 == a 

其中0 <= r2 < c0 <= r3 < b

两件相同的东西是相等的,所以我们有

 q1 * b * c + r1 == q2 * b * c + b * r2 + r3 

假设q1 == q2 + x为某个整数x 。 代入并解决x

 q2 * b * c + x * b * c + r1 = q2 * b * c + b * r2 + r3 x = (b * r2 + r3 - r1) / (b * c) 

哪里

  0 <= r1 < b * c 0 <= r2 < c 0 <= r3 < b 

x可以大于零? 不,我们有不平等:

  b * r2 + r3 - r1 <= b * r2 + r3 <= b * (c - 1) + r3 < b * (c - 1) + b == b * c 

所以这个分数的分子总是小于b * c ,所以x不能大于零。

x可以小于零吗? 不,相似的论点,留给读者。

因此整数x是零,因此q1 == q2

如果bc的绝对值低于sqrt(2^31) (约46 300),那么b * c将永远不会溢出,这些值将始终匹配。 如果b * c溢出,则可以在checked上下文中抛出错误,或者可以在unchecked上下文中获取不正确的值。

避免别人注意到的溢出错误,他们总是匹配。

假设a/b=q1 ,即a=b*q1+r1 ,其中0<=r1<b
现在假设a/b/c=q2 ,即q1=c*q2+r2 ,其中0<=r2<c
这意味着a=b(c*q2+r2)+r1=b*c*q2+br2+r1
为了a/(b*c)=a/b/c=q2 ,我们需要有0<=b*r2+r1<b*c
但是根据需要, b*r2+r1<b*r2+b=b*(r2+1)<=b*c ,并且这两个操作匹配。

如果bc是负数,这是行不通的,但我不知道在这种情况下整数除法是如何工作的。

我会提供我自己的乐趣certificate。 这也忽略了溢出,只能处理积极的不幸的是,但我认为certificate是清晰明了的。

目标是certificate这一点

floor(floor(x/y)/z) = floor(x/y/z)

在哪里/是正常的划分(贯穿这个certificate)。

我们将a/b的商和余数独特地表示a = kb + r (由此我们表示k,r是唯一的并且也注意到|r| < |b| )。 那么我们有:

 (1) floor(x/y) = k => x = ky + r (2) floor(floor(x/y)/r) = k1 => floor(x/y) = k1*z + r1 (3) floor(x/y/z) = k2 => x/y = k2*z + r2 

所以我们的目标是显示k1 == k2 。 那么我们有:

 k1*z + r1 = floor(x/y) = k = (xr)/y (from lines 1 and 2) => x/y - r/y = k1*z + r1 => x/y = k1*z + r1 + r/y 

因此:

 (4) x/y = k1*z + r1 + r/y (from above) x/y = k2*z + r2 (from line 3) 

现在从(2)可以看出, r1是一个整数(对于k1*z是一个定义的整数)和r1 < z (也是定义)。 此外从(1)我们知道r < y => r/y < 1 。 现在考虑(4)中的和r1 + r/y 。 要求是r1 + r/y < z并且从前面的权利要求中可以清楚地看出(因为0 <= r1 < zr1是一个整数,所以我们有0 <= r1 <= z-1因此0 <= r1 + r/y < z )。 因此根据r1 + r/y = r2的定义r1 + r/y = r2 (否则将会有两个 x/y的余数与余数的定义相矛盾)。 因此我们有:

 x/y = k1*z + r2 x/y = k2*z + r2 

我们有我们所期望的结论: k1 = k2

上面的证据应该与消极的工作,除了几个步骤,你需要检查一个额外的案件(S)…但我没有检查。

计数器示例:INT_MIN / -1 / 2