固定寬度整數是否分配乘法？

Question

對於三位n位有符號整數a,b和c（如32位），a * (b + c) == (a * b) + (a * c)是否總是如此，考慮到整數溢出？

我認爲這是獨立於語言的，但如果不是，我特別關心Java的答案。

Answer 1

是的，它成立，因爲整數運算是有限環上的模運算。

你可以看到一些理論探討，在這裏：https://math.stackexchange.com/questions/27336/associativity-commutativity-and-distributivity-of-modulo-arithmetic

Answer 2

是的，這是始終爲真。

它是一個屬性，因爲你有效地進行算術模2^32。事實上，簽名會使事情稍微複雜化（並且意味着你不能假設你正在做一般的模運算的等價物），但不會影響這個特定的分配屬性。

一個想法實驗是考慮使用重複添加來實現它，並考慮它溢出時會發生什麼。由於添加順序不會影響ints（即使有溢出）的結果，因此也不會按照不同順序重複添加。並且由於int乘法總是等於重複加法，因此對於重新排序的乘法，結果也必須相同。證明完畢

Answer 3

是的，它確實適用於Java，包括溢出情況。 （某些其他語言沒有指定溢出行爲，在這種情況下不提供任何保證。）

Answer 4

分配律適用於模運算;因爲固定位長度的二進制補碼整數運算是homomorphic以對相同（無符號）比特長度進行模運算，所以當使用二進制補碼運算時，分配屬性成立。

可以找到更詳細的解釋here。

Answer 5

對於2對符號整數的補數學問題歸結爲：

is (a*(b+c))%(2**32) === (a*b+a*c)%(2**32) 

所以對2的補符號整數運算，它總是如此。

對於非2的補碼有符號整數運算，我猜這取決於如何處理溢出。如果它反映了模數學，那麼這是事實。