【證明】加減法交換兩個整數，過程可能會溢出，但結果依然正确

請對下面的代碼做出判斷：

void swap_int(int *a,int *b)
{
  if(a == b)
	return;
  *a=*a+*b;
  *b=*a-*b;
  *a=*a-*b;
}
           

以下說法正确的是：

A.結果不正确，因為會溢出，用位與的方式就沒問題

B.結果正确，即使會溢出

C.結果正确，不會溢出

D.其他選項都不對

答案是B 結果正确，即使會溢出。

因為如果是兩個正整數相加，則先發生一次上溢，後面發生兩次下溢，進而結果正确。

如果是兩個負整數，則先發生一次下溢，後面發生兩次上溢，進而結果也正确。

詳細分析如下：

我們記待交換的兩個數為A、B

設整形變量*a、*b的位表示為 *a = n31n30 ··· n0 *b = m31m30 ··· m0 隻有當(*a > 0 && *b > 0) 或 (*a < 0 && *b < 0)時才會發生溢出。 兩者類似，不失一般性，我們隻證明A、B均大于0時的情況。 A與B均大于0時求和發生的溢出隻可能是上溢。 所謂溢出，就是說，必須擴充額外一位才能夠容納正确的結果，我們記 '|'的左邊為擴充位。 *a = 0|0a30 ··· a0 = a30*230 +  a29*229 + ··· + a0*20 = A *b = 0|0b30 ··· b0 = b30*230 +  b29*229 + ··· + b0*20 = B 因為這裡我們考察的是正數，是以對于擴充後的低32位，所有位均表示值，沒有符号位。 也就是說，把擴充後的第33位看作是符号位。 對于32位時的上溢，用33位 表示必為 *a + *b = 0|1n30 ··· n0 = 231 + n30*230 +  n29*229 + ··· + n0*20 =  2 31  + K ①  計算機将得到的33位結果truncate回原來的32位，即丢棄第33位(0)變為： *a + *b =    1n30 ··· n0 = -231 + n30*230 +  n29*229 + ··· + n0*20 = -2  31   + K ②

A+B的應該值是①，而實際上溢結果為②，可見上溢結果=應該值-2 32   即② = ① -  232 此時*a中存儲的就是②=A+B - 232 當溢出發生時，我們來看第二句指派語句： *b = *a - *b = ② - *b =  A+B - 232 - B  = -232 + A 因為 -232 對于32位的int來說，就是0，下溢，使得-232 + A  == A，即*b = A; 第二句指派語句正确。

下面再來看第三句指派語句： *a=*a-*b = ② - *b =  A+B - 232 - A = -232 + B

又一次發生下溢，使得-232 + B  == B，即*a = B;

綜上所述，是以盡管溢出了，但仍能正确交換。

=================================================

更新内容：

有人私信我說，對于兩個正整數相加溢出，比較好了解，因為此時上溢的那一位并沒有丢失，而是存儲到了符号位。整型數字在運算時，并沒有什麼符号的概念，都是做的加法。符号位隻在解釋二進制位的時候才有用，而在操作的時候和其他位是一樣的。也就是說，正整數加法并沒有丢失位資訊。

但是負整數呢？負數相加下溢時，進位的1丢失了。還能保證結果正确嗎。

答案是：還能保證結果正确。

對負整數相加時溢出進行一下分析。

當A、B小于0 且 A+B 下溢時：

為便于分析，仍擴充為33位

*a = 0|1a30 ··· a0 =-231 + a30*230 +  a29*229 + ··· + a0*20 = A *b = 0|1b30 ··· b0 = -231 + b30*230 +  b29*229 + ··· + b0*20 = B 現在，對于請将擴充位看作是符号位，剩餘的低32位均表示值。 根據雙符号位法則，若兩個符号位的得值不同（01或10）則是溢出。01表明兩個正數相加,結果大于機器所能表示的最大正數,稱為"上溢"；10表明兩個負數相加,結果小于機器所能表示的最小負數,稱為"下溢"； ① 為應該值，②為下溢值

對于32位時的下溢，用33位 表示必為 *a + *b = 1|0n30 ··· n0 = -232 + n30*230 +  n29*229 + ··· + n0*20 =  -2 32  + K ①  計算機将得到的33位結果truncate回原來的32位，即丢棄第33位(1)變為： *a + *b =    0n30 ··· n0 = -231 + n30*230 +  n29*229 + ··· + n0*20 = K ②

A+B的應該值是①，而實際下溢結果為②，可見下溢結果=應該值 + 2 32   即② = ① +  232 此時*a中存儲的就是②=A+B+ 232 當溢出發生時，我們來看第二句指派語句： *b = *a - *b = ② - *b =  A+B + 232 - B  = 232 + A 因為 232 對于32位的int來說，就是0，是一次上溢，使得 232 + A  == A，即*b = A; 第二句指派語句正确。

下面再來看第三句指派語句： *a=*a-*b = ② - *b =  A+B + 232 - A = 232 + B

又一次發生上溢，使得232 + B  == B，即*a = B;

綜上所述，是以盡管溢出了，但仍能正确交換。