題目連結：
題目大意：
給定一正整數 N （4 ≦ N ≦ 4 × 10 ^ 6），代表接下來有 N 個整數（可存於 int 型態內）。
這 N 個整數中，有一個數字只出現一次，其他數字都有出現過三次。求只出現過一次的那個數字。
記憶體限制：５ＭＢ。
範例輸入：
4
2 2 2 1
範例輸出：
1
解題思維：
（2023 / 5 / 22 更新：原先的程式碼太慢了。但是新程式碼的作法與下列作法核心本質上是一樣，因此保留。)
假設給定 10 個數字為 1 、 2 、 2 、 2 、 3 、 3 、 3 、 4 、 4 、 4，則把這 10 個數字轉成二進位之後並排成一行且靠右對齊如下，則我們可以看到其位數的總和：
１
１０
１０
１０
１１
１１
１１
１００
１００
１００
＿＿＿＿＿
＋)３６４
可以看到只有最右邊的位元的「1」之總數並非 3 的倍數，而最右邊的位元代表 2 ^ 0 ＝ 1。因此只出現一次的數字即為 1 。
而推廣到其他情況則是，統計在所有數字中對應的位元有多少個「1」。如果此位置的位元「1」之總數不為 3 的倍數，則代表所求數字的這個位元之值為「1」（有這個位元）。
因為其他數字都出現過 3 次，所以相應位元數總和應為 3 的倍數。但因為有一個數只出現一次，因而造成上述的性質。
因為測試資料很大，所以只能用 scanf 、 getchar ，甚至是自己寫的輸出入函式（參見這題）。
（2023 / 5 / 22 更新：以下是新程式碼的作法。）
原先的作法是把每一個位元分開各自統計，然後在最後的時候把所有統計次數不為 3 的倍數的位元找出來。這樣會有點慢（因為要自行地掃過每一個位元）。
而我們可以用內建的位元運算來同時統計每一個位元的次數，並且我們直接把最後模 3（即求除以 3 的餘數）的步驟也用位元運算 + 狀態轉移來處理。
因此我們定義三個變數 C0 、 C1 、 C2，分別代表在目前狀態下哪些位元出現了 3k 、 3k + 1 或 3k + 2 次，其中 k 為某非負整數（其實際值不重要。可以看到這邊隱含了模 3 之性質） 。
例如說，C0 = 0011 、 C1 = 1100 、 C2 = 0000（注意這邊是以二進位制顯示）代表著最右邊兩個位元在目前掃過的數字出現的次數恰好為 3 的某個倍數（以下簡稱其值為 0，因為我們要考慮的是模 3 後的出現次數之值）、而最左邊兩個位元之次數則為 3 的某個倍數 + 1（以下簡稱其值為 1），而沒有任何位元出現次數為 3 的某倍數 + 2（以下簡稱其值為 2）。
而我們仔細一看可以發現 C0 的值根本不重要（畢竟都已經是 3 的倍數，可以直接歸零重新計算）。因此我們把它的定位重新定義成「考慮現在新看到的數字後哪些位元出現次數變為 0」。
因此（假設現在新看到的數字為 n），C0 在新數字進來時的值應為 C2 & n，其中 & 代表位元運算中的 AND 之操作。因為 C2 代表著次數為 2 的位元們，而這個時候如果相同位置的位元在 n 也有出現則代表出現次數要加 1，因此次數會變為 0（當然不是真的 0，只是與 0 次等價）。
接著我們要更新 C1 和 C2 的值。
首先我們要消掉 C2 中次數變成 0 的那些位元，因此我們把 C2 之值更新為 C2 ^ C0，其中 ^ 代表著位元運算中 XOR 之操作。同樣地，我們對 n 做類似的事情——即將其值更新為 n ^ C0。
這樣一來，C2 和 n 都只剩下還未被考慮的位元們。
而 C2 在這個階段的最終值應為 C2 | (C1 & n)，其中 | 代表著位元運算中 OR 之操作。因為我們要把 C1 中次數變成 2 的位元們加到 C2 之中（這樣不會與 C2 原先位元衝突，是因為不會有位元在先前的數字中同時滿足出現次數為 1 次和 2 次）。
而 C1 的最終值應為 C1 ^ n（與上面 C2 的中繼值 C2 ^ C0 同理）。
總結，以下便是更新「所有位元」的出現次數應做的狀態轉移之操作：
C0 = C2 & n
C2 = C2 ^ C0
n = n ^ C0
C2 |= C1 & n
C1 = C1 ^ n
而最後根據定義，C1 是 N 個數字中出現次數為 1 的位元們。因此 C1 即為所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
