1863. 找出所有子集的异或总和再求和

题目

一个数组的 异或总和 定义为数组中所有元素按位 XOR 的结果；如果数组为 空 ，则异或总和为 0 。

• 例如，数组 [2,5,6] 的 异或总和 为 2 XOR 5 XOR 6 = 1 。

给你一个数组 nums ，请你求出 nums 中每个 子集 的 异或总和 ，计算并返回这些值相加之 和 。

**注意：**在本题中，元素 相同 的不同子集应 多次 计数。

数组 a 是数组 b 的一个 子集 的前提条件是：从 b 删除几个（也可能不删除）元素能够得到 a 。

示例 1：

输入：nums = [1,3]
输出：6
解释：[1,3] 共有 4 个子集：
- 空子集的异或总和是 0 。
- [1] 的异或总和为 1 。
- [3] 的异或总和为 3 。
- [1,3] 的异或总和为 1 XOR 3 = 2 。
0 + 1 + 3 + 2 = 6

示例 2：

输入：nums = [5,1,6]
输出：28
解释：[5,1,6] 共有 8 个子集：
- 空子集的异或总和是 0 。
- [5] 的异或总和为 5 。
- [1] 的异或总和为 1 。
- [6] 的异或总和为 6 。
- [5,1] 的异或总和为 5 XOR 1 = 4 。
- [5,6] 的异或总和为 5 XOR 6 = 3 。
- [1,6] 的异或总和为 1 XOR 6 = 7 。
- [5,1,6] 的异或总和为 5 XOR 1 XOR 6 = 2 。
0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28

示例 3：

输入：nums = [3,4,5,6,7,8]
输出：480
解释：每个子集的全部异或总和值之和为 480 。

提示：

• 1 <= nums.length <= 12
• 1 <= nums[i] <= 20

---

解题思路

异或（XOR）是一种位运算，它的规则可以简单理解为“相同为0，不同为1”。

用两个循环来解决(这道题的数据量不是很大，可以暴力枚举！)

1. 外层循环：遍历所有可能的子集（用二进制位表示）
2. 内层循环：检查当前子集包含哪些元素，并计算这些元素的异或总和。

分步拆解（以 3,4,5,6,7,8 为例）

外层循环：遍历所有子集

for (int i = 0; i < (1 << 6); i++)

• i 从 0 到 63（二进制 000000 到 111111），每个 i 的二进制表示对应一个子集的选择方式。
• 例如：
  • i = 0（000000）：不选任何元素 → 子集 []。
  • i = 1（000001）：选第0位 → 子集 [3]。
  • i = 2（000010）：选第1位 → 子集 [4]。
  • i = 3（000011）：选第0和第1位 → 子集 [3, 4]。
  • …
  • i = 63（111111）：选所有元素 → 子集 [3, 4, 5, 6, 7, 8]。

---

内层循环：检查当前子集包含哪些元素

for (int j = 0; j < 6; j++)

• j 从 0 到 5，检查 i 的第 j 位是否为 1（即是否选中 nums[j]）。
• (1 << j) 生成一个只有第 j 位是 1 的数字：
  • j = 0：1 << 0 = 1（二进制 000001）。
  • j = 1：1 << 1 = 2（二进制 000010）。
  • …
  • j = 5：1 << 5 = 32（二进制 100000）。
• (i & (1 << j)) != 0：
  • 如果结果为 true，表示选中 nums[j]，将其异或到 ans 中。

---

示例演示（选取几个典型的 i 值）

1. i = 0（000000）

• 子集：[]。
• 内层循环：
  • j = 0：0 & 1 = 0 → 不选 3。
  • j = 1：0 & 2 = 0 → 不选 4。
  • …
  • j = 5：0 & 32 = 0 → 不选 8。
• ans = 0（初始值）。
• res += 0 → res = 0。

2. i = 1（000001）

• 子集：[3]。
• 内层循环：
  • j = 0：1 & 1 = 1 → 选 3 → ans = 0 ^ 3 = 3。
  • j = 1：1 & 2 = 0 → 不选 4。
  • …
  • j = 5：1 & 32 = 0 → 不选 8。
• ans = 3。
• res += 3 → res = 3。

3. i = 3（000011）

• 子集：[3, 4]。
• 内层循环：
  • j = 0：3 & 1 = 1 → 选 3 → ans = 0 ^ 3 = 3。
  • j = 1：3 & 2 = 2 → 选 4 → ans = 3 ^ 4 = 7。
  • j = 2：3 & 4 = 0 → 不选 5。
  • …
  • j = 5：3 & 32 = 0 → 不选 8。
• ans = 7。
• res += 7 → res = 10。

4. i = 63（111111）

• 子集：[3, 4, 5, 6, 7, 8]。
• 内层循环：
  • j = 0：63 & 1 = 1 → 选 3 → ans = 0 ^ 3 = 3。
  • j = 1：63 & 2 = 2 → 选 4 → ans = 3 ^ 4 = 7。
  • j = 2：63 & 4 = 4 → 选 5 → ans = 7 ^ 5 = 2。
  • j = 3：63 & 8 = 8 → 选 6 → ans = 2 ^ 6 = 4。
  • j = 4：63 & 16 = 16 → 选 7 → ans = 4 ^ 7 = 3。
  • j = 5：63 & 32 = 32 → 选 8 → ans = 3 ^ 8 = 11。
• ans = 11。
• res += 11 → res = …（累加中）。

---

关键点总结

1. 外层循环：i 的二进制位表示子集的选择状态（0 到 63）。
2. 内层循环：用 (i & (1 << j)) != 0 判断是否选中 nums[j]。
3. 异或计算：只有选中的元素才会参与异或（初始 ans = 0）。
4. 结果累加：每个子集的异或总和独立计算后累加到 res。

---

完整代码

class Solution {
    public int subsetXORSum(int[] nums) {
        int res=0;
        int n=nums.length;
        for(int i=0;i<(1<<n);i++){
            int ans=0;
            for(int j=0;j<n;j++){
                if((i&(1<<j))!=0)   ans^=nums[j];
            }
            res+=ans;
        }
        return res;
    }
}