主題
題目連結：
題目意譯：
一個陣列的 XOR 總計定義為其所有元素按位元 XOR 之值，抑或是 0 如果陣列為空。
例如，[2,5,6] 的 XOR 總計為 2 XOR 5 XOR 6 = 1 。
給定一陣列 nums ，回傳所有 nums 的子集合之 XOR 總計的總和。
注：有著同樣元素的子集合應被納入多次。
一個陣列 a 為陣列 b 的子集合，如果 a 可以從 b 藉由刪除一些（可能沒有）元素而得到。
限制：
1 ≦ nums.length ≦ 12
1 ≦ nums[i] ≦ 20
範例測資：
範例 1：
輸入： nums = [1,3]
輸出： 6
解釋： [1,3] 的 4 個子集合為：
- 空集合有著 XOR 總計為 0 。
- [1] 有著 XOR 總計為 1 。
- [3] 有著 XOR 總計為 3 。
- [1,3] 有著 XOR 總計為 1 XOR 3 = 2 。
0 + 1 + 3 + 2 = 6
範例 2：
輸入： nums = [5,1,6]
輸出： 28
解釋： The 8 subsets of [5,1,6] are:
- 空集合有著 XOR 總計為 0 。
- [5] 有著 XOR 總計為 5 。has an XOR total of 5.
- [1] 有著 XOR 總計為 1 。has an XOR total of 1.
- [6] 有著 XOR 總計為 6 。has an XOR total of 6.
- [5,1] 有著 XOR 總計為 5 XOR 1 = 4 。
- [5,6] 有著 XOR 總計為 5 XOR 6 = 3 。
- [1,6] 有著 XOR 總計為 1 XOR 6 = 7 。
- [5,1,6] 有著 XOR 總計為 5 XOR 1 XOR 6 = 2 。
0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28
範例 3：
輸入： nums = [3,4,5,6,7,8]
輸出： 480
解釋： 所有子集合的 XOR 總計之總和為 480 。
解題思維：
雖然可以直接將所有可能的子集合窮舉出來並求得每個子集合的 XOR 總計之值，然後將這些值加起來得到所求。
不過，假設我們現(xiàn)在有著 K = nums.length 個數(shù)字。而這 K 個數(shù)字的二進位表示法之中，有 X 個數(shù)字在第 B 個位元（2 ^ B ， 0 ≦ B）是「1」、而 Y 個數(shù)字在第 B 位元為「0」。
理所當然地，X + Y = K。而這些 2 ^ K 個子集合之中，在第 B 位元為「1」的會有
2 ^ (K - 1)
個。因為那 Y 個數(shù)字挑或不挑都不影響第 B 位元是不是「1」，而挑法會有 2 ^ Y 種；而真的會影響第 B 位元為「1」的是那 X 個數(shù)字，總挑法有 2 ^ X 種，但是只有其中一半的挑法才會讓該位元為 1 （那 X 個數(shù)字挑偶數(shù)個時，會使得該位元 XOR 的結果為「0」；奇數(shù)個才會使其為「1」）。因而得出了挑法為 2 ^ (X - 1) × 2 ^ Y = 2 ^ (X + Y - 1) = 2 ^ (K - 1) 的結論。
而這可以適用於每個位元上（只要給定的 K 個數(shù)字在該位元有任何一個數(shù)字為「1」）。
因此，我們可以掃過這 K 個數(shù)字，統(tǒng)計每個位元是否曾在這 K 個數(shù)字中為「1」，而這可以利用位元運算 OR 而得到。例如我們有以下 3 個數(shù)字：
5 1 4
而它們的二進位表示法依序為
101
001
100
全部 OR 起來我們便得到
101
代表 2 ^ 0 、 2 ^ 2 在這 3 個數(shù)字中曾為「1」。在此，我們將所有數(shù)字 OR 後的結果稱為 M 。
而因為我們要求的是 XOR 總計的「總和」，而對於第 B 位元（其曾為「1」），其會在「總和」中貢獻 2 ^ B × 2 ^ (K - 1) 之值。因此在上例中，我們會得到
2 ^ 0 × 2 ^ (3 - 1) + 2 ^ 2 × 2 ^ (3 - 1)
可以看到有共同項 2 ^ (3 - 1) = 2 ^ 2 ，所以我們提出去得到
(2 ^ 0 + 2 ^ 2) × 2 ^ 2
而括號中的即是 5 、 1 、 4 這 3 個數(shù)字 OR 後所得到的 M 值。而任何數(shù)字組合都會得到一樣的結果。
因此，所求便可以簡化為
M × 2 ^ (K - 1)
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
