題目連結：
題目大意：
給定一正整數 ｎ （ｎ ≦ １００, ０００），代表接下來的一列輸入有 ｎ 個整數 ａ１ 、 ａ２ 、 …… 、 ａｎ （０ ≦ ａｉ ＜ ２ ^ ６０）。
設一數字在二進位表示法下有奇數個「1」，定義其 parity 為 1 ；反之，若有偶數個，則定義 parity 為 0 。
求有多少數對（ａｉ, ａｊ）（其中 ｉ ＜ ｊ），ａｉ ＸＯＲ ａｊ 之 parity 為 0 。
範例輸入：
2
1 2
3
1 2 3
範例輸出：
1
1
解題思維：
經過一些 XOR 運算的例子：
１１０
００１
XOR 得
１１１
１０１
００１
XOR 得
１００
０１１
００１
XOR 得
０１０
１００
００１
XOR 得
１０１
０１０
００１
XOR 得
０１１
００１
００１
XOR 得
０００
１１０
０１１
XOR 得
１０１
１０１
０１１
XOR 得
１１０
０１１
０１１
XOR 得
０００
以上，我們可以觀察出 parity 為 0（以下稱偶同位）與 parity 為 1 （以下稱奇同位）做 XOR 後的數字必為奇同位；同樣地，奇同位與奇同位 XOR 得偶同位的數字；以及偶同位與偶同位數字 XOR 必得偶同位的數字。以下是原因：
假設第一個數字有 ｘ 個「1」，第二個數字有 ｙ 個「1」。則兩數 XOR 後，新的數會有 ｘ ＋ ｙ － ｃ 個「1」，其中 ｃ ≦ ｘ ＋ ｙ 且 ｃ 必為偶數。而 ｃ 必是偶數的原因在於
1 XOR 1 ＝ 0 、 1 XOR 0 ＝ 1 、 0 XOR 1 ＝ 1
所以每次有「1」在 XOR 後消失是一次消失兩個「1」（因為上式的緣故，且 0 XOR 0 ＝ 0 也不會影響最後「1」的數量）。
而正因為 ｃ 是偶數，所以單看 ｘ 、 ｙ 的奇偶性來推測出 ｘ ＋ ｙ 的奇偶性，進而得知最後是奇同位還是偶同位。而
奇數 ＋ 奇數為偶數 → 偶同位
奇數 ＋ 偶數為奇數 → 奇同位
偶數 ＋ 偶數為偶數 → 偶同位
這就是一開始觀察到的規律。
回到題目的所求，我們需要求出滿足 XOR 後為偶同位（parity 為 0）的所有數對。根據上面的規律，我們只需要統計出給定的數字們有多少是奇同位（數量為 ａ）、多少是偶同位（數量為 ｂ），則答案即為：
［ａ × （ａ － １） ÷ ２］ ＋ ［ｂ × （ｂ － １） ÷ ２］
但是對於每個數字一個位元一個位元地去數有幾個「1」還是有點慢（每個數字 ６４ 位元，也就是每次都會有 ６４ 個步驟）。而以下的方法可以快速地得出一數字 ｐ 是奇同位還是偶同位：
ｐ ← ｐ XOR （ｐ ＞＞ ３２）
ｐ ← ｐ XOR （ｐ ＞＞ １６）
ｐ ← ｐ XOR （ｐ ＞＞ ８）
ｐ ← ｐ XOR （ｐ ＞＞ ４）
ｐ ← ｐ XOR （ｐ ＞＞ ２）
ｐ ← ｐ XOR （ｐ ＞＞ １）
其中 ＞＞ ｃ 代表所有位元「右移」 ｃ 位元。
最後再看 ｐ 的最後一位元是「1」還是「0」。前者即奇同位，後者則是偶同位。而此原理就是一次將數字切一半，左邊那半 XOR 右邊那半。重複做到剩下最後一個位元的時候，即可知道所有位元 XOR 彼此的結果。
設 ｐ ＝ ｂ０ ｂ１ …… ｂ６４ ，則結果為 ｂ０ ＸＯＲ ｂ１ ＸＯＲ …… ＸＯＲ ｂ６４ 。結果是「1」或是「0」正好代表了原本「1」的個數之奇偶性（偶數個「1」結果剛好通通抵銷所以是「0」；反之若為奇數個，最後會剩一個「1」沒被抵銷）。
最後要注意的兩點是：資料量挺多的，請最佳化輸出入、結果可能會超過 int 所能儲存的範圍，請愛用 long long 型態。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人