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

Question

设a,b和c为非大正整数.a/b/c是否始终等于/(b*c)与C#整数运算？对我来说,在C#中它看起来像:

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

所以我的问题是:x1 == x2为所有a,b和c做什么？

Answer 1

我非常喜欢这个问题,于2013年6月4日将其作为我博客的主题.谢谢你这个好问题!

大案件很容易找到.例如:

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

因为b * c溢出为负数.

我想补充到这一事实,在检查算术,之间的差异a / (b * c),并(a / b) / c可以是工作的程序和崩溃的程序之间的差异.如果产品b和c溢出的整数的范围那么前者将在检查范围内崩溃.

对于小的正整数,比如说小到足以适应短的整数,应该保持身份.

蒂莫西·希尔兹刚刚发布了证据; 我在这里提出另一种证据.假设这里的所有数字都是非负整数,并且没有任何操作溢出.

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

所以该师a / (b * c)找到了q1这样的价值

q1 * b * c + r1 == a

哪里 0 <= r1 < b * c

划分( a / b ) / c第一发现值qt,使得

qt * b + r3 == a

然后发现值q2,使得

q2 * c + r2 == qt

所以替换为in qt,我们得到:

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

在哪里0 <= r2 < c和0 <= 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.

Answer 2

设\表示整数除法(/两个ints 之间的C#运算符),并/表示通常的数学除法.然后,如果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]解释如下.假设您有两个整数a和范围内b的小数.很容易看出来f[0, 1)

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

如果在行中[1]你识别a = floor(x / y),f = (x / y) - floor(x / y)和b = z,那么[3]暗示[1]并且[2]相等.

您可以将此证明推广为负整数(仍然忽略溢出),但我会将其留给读者以保持简单.

关于溢出问题- 请参阅Eric Lippert的答案以获得一个很好的解释!他在博客文章中也采取了更加严谨的方法并回答,如果你觉得我太过手淫,你应该考虑一下.