位運算的巧妙使用 -- 交換兩個值

引言

我們都知道，在程式代碼中，位運算的計算時間是比較短的，相比加減法乘除法來說，是以，我們經常會在核心代碼，或者一些要求運算速度的場景中看到使用位運算的，接下來就介紹兩個位運算的巧妙運用吧。

不使用多餘的空間交換兩個值

考慮一個 swap 函數，它可以将 a 與 b 的值進行交換，我們可以寫出使用指針的版本：

template <typename T>
void swap(T *a, T *b){
                T temp = *a;
          *a = *b;
          *b = temp;
}      

這樣看我們其實使用了一個局部變量 temp，那麼我們能否在不使用局部變量的情況下實作兩個數值的交換呢？我們先來看看第一種簡單的方法，使用加減法：

int a = 1;
int b = 2;
//swap by +/-
a = a + b;
b = a - b;        //b = (a + b) - b = a
a = a - b;        //a = (a + b) - b = (a + b) - a = b      

可以發現，這種方法實際上是先将 a+b 指派給 a，再計算 b(實際上要給 b 指派之前 a 的值)，是以用 a-b 就得到了舊的 a 值，同理，最後一步 a=a-b 也計算出了 b 的值，達成了交換的目的。

int a = 1;
int b = 2;
//swap by ^
a = a ^ b;
b = a ^ b;        //b = (a ^ b) ^ b = a ^ (b ^ b) = a ^ 0 = a;
a = a ^ b;        //a = (a ^ b) ^ a = a ^ b ^ a = b;