通常我們實作兩數交換不得不引入一個臨時變量temp作為媒介,而使用異或運算也能實作同樣的功能,甚至無需使用臨時變量。
這是一個通常的做法:
int main(){
int a=1,b=2,temp;
temp=a;
a=b;
b=temp;
printf("%d,%d\n",a,b);
return 0;
}
關于異或(Exclusive OR)
Wikipedia解釋
在數位邏輯中,邏輯算符互斥或閘(exclusive or)是對兩個運算元的一種邏輯分析類型,符号為XOR或EOR或⊕。與一般的或閘OR不同,當兩兩數值相同為真..而有一數值不同時為否..
兩個運算元(命題):A與B的異或一般寫成A異或B,或者寫成

、
、
等等。在C語言中,寫作A^B。
異或真值表
A | B | A^B |
1 | 1 | |
1 | 1 | |
1 | 1 |
異或的小例子
假設a為二進制數01,b為二進制數10,a^b的結果為11并将其存儲在變量c中,經過反複的測試,于是發現以下的規律:
11^01=10
11^10=01
c^a=b;
c^b=a;
可以很驚奇的發現,将兩數異或的結果與其中一數再進行異或,可以得到另一個數。
原理很簡單,兩數異或的結果儲存了兩個數上每一個二進制位不同或相同的資訊,如果相應的二進制位不同,就标志為1,如果相同,則标志為0。
由于任意一個二進制位與1異或有這樣一個特性:
0^1=1
1^1=0
即與1異或後,都将自己轉換成相反的位
這樣,我們就使用異或運算交換了兩數
12(001100)
^ 34(100010)
-------------------
101110
101110 ^ 001100=100010
101100 ^ 100010=001100
int main(){
int a=12,b=34,temp;
printf("Original result: a=%d,b=%d\n",a,b);
temp=a^b;
a=temp^a;
b=temp^b;
printf("Transformed result: a=%d,b=%d\n",a,b);
return 0;
}
result //
Original result: a=12,b=34
Transformed result: a=34,b=12
但是使用這種方法似乎與使用臨時變量沒有什麼差別?
其實不然,通過簡單分析可以發現臨時變量的值在整個過程中并沒有發生變化,是以也可以無需設定臨時變量。
a=a^b^a;
b=a^b^b;
于是可以使用第三種方法,将a設定為臨時變量
a=a^b;
b=b^a;
a=b^a;
還可以寫得更簡潔一點:
a^=b^=a^=b;