天天看點

使用異或運算實作兩數交換

通常我們實作兩數交換不得不引入一個臨時變量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;
           

繼續閱讀