在C＃整數運算中，a/b/c總是等於a /（b * c）？

設a，b和c爲非大正整數。用C＃整數算術，a/b/c總是等於a /（b * c）嗎？對我來說，在C＃中，它看起來像：在C＃整數運算中，a/b/c總是等於a /（b * c）？

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

所以我的問題是：x1 == x2所有A，B和C？

來源

2013-05-30 Jason Crease

這是一個數學問題，而不是編程問題。你能解釋這個問題的編程特定部分是什麼嗎？ – Oded

+38

@在任何有理數的範圍內，當然，但這是專指整數算術（在C＃中）。 IMO使其與編程相關。也許a/b/c == a /（b * c）在整數運算中存在的規則，也許它只在有理數運算中成立。 –

+43

這是一個關於C＃的完全合理的問題，並且很容易回答。 –

讓\分別表示整數除法（二int S之間的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和範圍[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]是相等的。

可以概括這個證明到負整數（仍然忽略溢出），但我把它留給讀者保持點簡單。

在溢出的問題 - 看埃裏克利珀的答案一個很好的解釋！他還參加了his blog post和答案，你應該看看，如果你覺得我太手工波浪更加嚴格的措施。

來源

2013-05-30 14:17:51

哈，那就是我之後:) – Rawling

我喜歡你使用\和/爲此。讓事情變得更加清晰。 –

@JustinMorgan這個符號實際上是用在其他一些編程語言中的（儘管我現在不記得哪一個）。 –

我很喜歡這個問題，我把它作爲my blog on June 4th, 2013的主題。感謝您的好問題！

大案件很容易來。例如：

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

因爲b * c溢出到一個負數。

我想補充到這一事實，在檢查算術，a/(b * c)和(a/b)/c之間的差異可能是一個可行的程序和崩潰的程序之間的差異。如果b和c的乘積溢出整數的範圍，則前者將在檢查的上下文中崩潰。

對於小的正整數，比如說小到可以放入一個短整數，應該保持身份。

Timothy Shields剛發佈了一個證明;我在這裏介紹另一種證據。假設這裏所有的數字都是非負整數，並且沒有任何操作溢出。的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

所以替代品在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。

來源

2013-05-30 13:49:17

+1同樣會崩潰，如果任一'b '或'c'爲零。 –

@JoseRuiSantos是的，但在這種情況下'x1' **和**'x2'操作都會發生同樣的崩潰 –

@JoseRuiSantos在兩種情況下都不是這樣嗎？ – Jodrell

如果b和c絕對值低於約sqrt(2^31)（約46 300），這樣，b * c絕不會溢出，這些值將總是匹配。如果b * c溢出，則存在錯誤，可在checked背景下拋出，或者你可以在unchecked方面不正確的值。

來源

2013-05-30 14:06:48

避免他人注意到的溢出錯誤，它們總是匹配。

讓我們假設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，根據需要，這兩個操作相匹配。

如果b或c是負數，這不起作用，但我不知道在這種情況下整數除法是如何工作的。

來源

2013-05-30 14:34:05 Teepeemm

我會提供我自己的樂趣證明。這也忽略了溢出，只能處理積極的不幸，但我認爲證明是清晰明瞭的。

的目的是要表明，

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

其中/是正常的分裂（在本證明）。

我們代表的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 = (x-r)/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 < z和r1是一個整數，所以我們有0 <= r1 <= z-1因此0 <= r1 + r/y < z）。因此r1 + r/y = r2定義爲r2（否則將存在兩個來自x/y的剩餘部分，這與餘數的定義相矛盾）。因此，我們有：

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

，我們有我們想要的結論，即k1 = k2。

上面的證據應該與否定，除了一些步驟，你需要檢查一個額外的案件......但我沒有檢查。

來源

2013-05-31 07:49:32 rliu

計數器示例：INT_MIN/-1/2

來源

2013-06-03 04:51:01 hustwcw

「讓a，b和c爲非大**正**整數。」 – Pang

這是一個有趣的案例（即-INT_MIN是溢出）。謝謝！ –

在C＃整數運算中，a/b/c總是等於a /（b * c）？

回答

相關問題