Trick 2.6 - 交換兩個數

交換兩個整數，我們可以利用 XOR 的小技巧來節省一個變數。

$$ \begin{align} x &\leftarrow x\oplus y\ y &\leftarrow y\oplus x\ x &\leftarrow x\oplus y \end{align}

$$

補充內容

關於 XOR 還有一個有趣的小應用：

若我們有 $$m$$ 條邊形成一棵有根樹。那麼我們可以把每一條邊用一個 bit 儲存下來，在每一個節點 $$v$$ 上儲存一個集合 $$S_v$$ 包含從樹根走到這個節點的所有邊集。由於每一條邊我們用一個 bit 儲存下來，我們可以把 $$S_v$$ 用一個整數來表示之。

這時候，給定兩個節點 $$u, v$$，在這棵樹上 $$u, v$$ 之間的唯一路徑，其上面的邊的集合恰好就是 $$S_u\oplus S_v$$，很酷吧！