EasyRating 1372
1863. Sum of All Subset XOR Totals
arraymathbacktrackingbit-manipulationcombinatoricsenumeration
解題說明
Sum of All Subset XOR Totals
題目描述：給定一個整數陣列 nums，計算所有非空子集的 XOR 總和之和。
解題思路：觀察位元性質。對於每一個位元位置，若 nums 中有至少一個數字在該位元為 1，那麼在 2^n 個子集中，恰好有 2^(n-1) 個子集的 XOR 在該位元為 1。因此答案為 (nums[0] | nums[1] | ... | nums[n-1]) × 2^(n-1)。先計算所有元素的 OR，再乘以 2^(n-1)。
C++ 解法
複雜度分析
時間複雜度：O(n) — 遍歷陣列一次計算 OR。
空間複雜度：O(1) — 只需常數額外空間。
虛擬碼
1. Compute OR of all elements in nums 2. Return OR_value * 2^(n-1) (equivalently: OR_value << (n-1))
其他解法
回溯枚舉 O(2^n)：枚舉所有子集，計算每個子集的 XOR 值並累加。n <= 12 時可行，直觀但效率低。
位元逐位分析：對每個位元位置獨立分析其對答案的貢獻。若有 c 個元素在該位元為 1，則恰有 2^(n-1) 個子集的 XOR 在該位元為 1（當 c >= 1 時）。等價於 OR 解法但推導過程更清楚。
延伸思考
- 若要計算所有子集的 AND 總和之和，公式如何變化？
- 若要計算所有子集的 OR 總和之和呢？
- 若 nums 中元素值可以為負數，XOR 的行為是否改變？