2007/11/23

使用 XOR 做變數交換

哈,在 legnaleurc 的部落格看到突然想起來做個筆記。

一般來說,大家在交換二個變數的時候,習慣會使用第三個變數來做暫存器,例如:
int a,b,c;
c = a;
a = b;
b = c;


不過徐弘洋大師曾經說過一個很神的方法,就是利用 XOR 的方式交換二個變數,方式如下:
int a,b,c;
a ^= b;
b ^= a;
a ^= b;


這種方法有什麼好處呢?以第一種作法時,電腦會將 CPU register 中的資料複製到 memory 中,而且會複製三次;以第二種作法時,電腦則是在 CPU register 中進行三次的邏輯運算。

大家都知道 CPU 以邏輯計算速度最快,再者,register 的存取速度又快於 memory。所以使用第二種方式進行變數交換的速度,會比第一種方式快非常多。

1 則留言: