位运算
找出所有子集的异或总和在求和
1863. 找出所有子集的异或总和再求和 - 力扣（LeetCode）
方法一：回溯暴力
枚举所有子集并计算异或和
class Solution {
List<Integer> list = new ArrayList<>();
int sum = 0;
public int subsetXORSum(int[] nums) {
dfs(nums,0);
return sum;
}
public void dfs(int[] nums,int start){
if(list.size() != 0){
int temp = list.get(0);
for(int i = 1 ; i < list.size() ; i++){
temp ^= list.get(i);
}
sum+=temp;
}
if(start == nums.length){
return;
}
for(int i = start;i < nums.length;i++){
list.add(nums[i]);
dfs(nums,i+1);
list.remove(list.size() - 1);
}
}
}方法二：灵神的数学法（死记吧，但愿能记住）
对于异或运算，每个比特位是互相独立的。我们可以先思考只有一个比特位的情况，也就是 nums 中只有 0 和 1 的情况（从特殊到一般）。
在这种情况下：
- 如果子集中有偶数个 1，那么异或和为 0；
- 如果子集中有奇数个 1，那么异或和为 1。
因此，关键是 —— 求出异或和为 1 的子集个数。
基本思路
设 nums 的长度为 n，且其中**至少包含一个 ****1**。
我们可以：
- **先拿出其中一个 **
**1**； - 剩下的
n - 1个数可以随便选或不选，一共有：
2 的 (n - 1) 次方种选法。
分两种情况分析：
- 如果这
n - 1个数中选了 偶数个 1：
再**加上我们拿出来的那个 ****1**，就构成了 **奇数个 ****1**，异或和为1。 - 如果这
n - 1个数中选了 奇数个 1：
**不加我们拿出来的那个 ****1**，还是奇数个1，异或和也为1。
所以，一共有 **2 的 (n - 1) 次方** 个子集的异或和为 1。
注意事项
- 这个结论与
nums中到底有多少个1无关。 - 只要有**至少一个 **
**1**，异或和为1的子集个数一定是：
2 的 (n - 1) 次方- 如果
nums中全是 0（没有任何 1），那就没有任何子集异或和为 1，结果为 0。
✅ 最终结论
在 nums 至少包含一个 1 的情况下：
异或和为 1 的子集个数 = 2 的 (n - 1) 次方
第一步：先看只有一个比特位的情况（0 和 1）
假设 **nums** 数组中的元素只有 **0** 和 **1**，我们现在关心的是哪些子集的异或和是 **1**。
回顾下异或的特性：
**0 ⊕ 0 = 0****1 ⊕ 1 = 0****1 ⊕ 0 = 1**- 异或的结果是根据有多少个
**1**来决定的**：**- **偶数个
**1**→ 异或和是 ****0** - **奇数个
**1**→ 异或和是 ****1**
- **偶数个
举个例子：
**比如 **nums = [1, 0, 1]**
****长度 ****n = 3**
所有子集（共 2³ = 8 个）：
| 子集 | 异或和 |
|---|---|
| [] | 0 |
| [1] | 1 |
| [0] | 0 |
| [1,0] | 1 |
| [1] | 1 |
| [1,1] | 0 |
| [0,1] | 1 |
| [1,0,1] | 0 |
异或和为 1 的子集：4 个
关键结论：
如果 **nums** 里至少有一个 **1**，那么「异或和为 1 的子集个数」是：
2^(n-1)** 个**
**原因是：
**我们可以先把一个 **1** 拿出来，剩下的 **n-1** 个数每个都可以选或不选（共 2^(n-1) 种情况）。然后根据异或的性质，奇偶变化保证我们能让最终结果为 1。
第二步：推广到多个比特位的数（不止 0 和 1）
比如 nums = [3, 2, 8]：
转为二进制：
3=00112=00108=1000
我们发现哪些「比特位」上有至少一个 1：
- 第 0 位（从右往左数）✅
- 第 1 位 ✅
- 第 3 位 ✅
→ 因为这些位中至少有一个数在该位上是 1
子集异或和的规律：
每个比特位可以单独考虑，因为异或是按位进行的。
对于每一位：
- 如果该位上在某个数中出现了
1 - 那么最终异或和中，这一位也会对一些子集贡献值
- 每一位的贡献是：
2^k × 2^(n-1)
（2^k是这一位的权重，比如第 3 位 = 8，2^(n-1)是子集数量）
具体到上面的例子：
n = 3- 有 3 位是 1：第 0 位、第 1 位、第 3 位
- 所以答案是：
复制编辑
(2^0 + 2^1 + 2^3) × 2^(n - 1)
= (1 + 2 + 8) × 2^2
= 11 × 4
= 44什么是“每一位的贡献”？
我们最终要算的是：所有子集的异或和之和。
每个数字是二进制的，比如 8 = 1000，就是第 3 位是 1，其他位是 0。
那么我们可以 按位分开算：
- 第 0 位的贡献是多少？
- 第 1 位的贡献是多少？
- 第 2 位的贡献是多少？
- ...
因为异或是逐位进行的，每一位互不干扰！
✅ 举个例子说明：
比如 nums = [3, 2, 8]，即：
| 数字 | 二进制 |
|---|---|
| 3 | 0011 |
| 2 | 0010 |
| 8 | 1000 |
你看第 0 位、1 位、3 位上都有 1 出现。
我们关心的是：这些位对所有子集异或和之和贡献了多少？
🔍 聚焦某一位，比如第 3 位（值是 8）
第 3 位的值 = 2^3 = 8
步骤 1⃣：看这一位在 nums 中是否出现过 1
→ 出现了（8 的第 3 位是 1）
步骤 2⃣：哪些子集的异或和在这一位是 1？
和之前“0/1 情况”一样，我们可以知道：
- 只要有奇数个在这一位是 1 的数参与异或，这一位就是 1
- 所以，那些子集，在这一位上会贡献
1 * 2^3 = 8
步骤 3⃣：有多少个这样的子集？
如果总共有 n 个数，只要有某一位出现了 1，那么我们可以选或不选这些数构成子集。
- 其中会有
2^(n-1)个子集的异或结果在这一位上是 1
这个来自前面我们讲过的结论（异或为 1 的子集个数是 2^(n-1)）
🧮 所以总结一下：
- **第 k 位的值 = **
**2^k** - 有
2^(n-1)个子集在这一位上异或结果是 1 - 每个这样的子集会为最终总和贡献
2^k
所以这一位的总贡献就是：
2^k × 2^(n-1)
✅ 更形象理解：
你可以把每个“有效的位”当作一个硬币，比如：
- 第 3 位是 1，相当于你有一个值为 8 的“硬币”
- 这个硬币被“贡献”了
2^(n-1)次 - 所以总贡献就是：8 *
2^(n-1)
🚀 举个完整例子
python
复制编辑
nums = [3, 2, 8]
n = 3
or_sum = 3 | 2 | 8 = 11 # 二进制是 1011 → 第 0, 1, 3 位是 1
res = or_sum * (2 ** (n - 1)) = 11 * 4 = 44这个 44 就是「所有子集的异或和的总和」。
int max = 0;
List<Integer> resList = new ArrayList<>();
List<Integer> list = new ArrayList<>();
public List<Integer> largestDivisibleSubset(int[] nums) {
}
public void dfs(int[] nums, int start){
if(start == nums.length){
if(list.size() > max){
max = list.size();
resList = new ArrayList(list);
}
return;
}
for(int i = start;i < nums.length;i++){
}
}List<Integer> list = new ArrayList<>();
Arrays.sort(nums);
list.add(nums[0]);
for(int i = 1; i < nums.length;i++){
if(nums[i] % list.get(list.size() - 1) == 0){
list.add(nums[i]);
}
}
return list;