---

数组中两个数的最⼤异或值

1. leet code：https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/description/
2. 暴力解法：【部分样例超时，通过不了，不可以行】

class Solution {
    public int findMaximumXOR(int[] nums) {
        int n = nums.length;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int temp = nums[i] ^ nums[j];
                if (temp > max)
                    max = temp;
            }
        }

        return max;
    }
}

3. 基于位操作的贪心解法
   解题流程：
   （1）题目要求整数32位，那就获取数组每个数的32位表达，二进制的01。
   （2）从最高位开始判断，存在两个数，在该位有0，1的表达（异或=1），那么我们答案的这一个为1。
   （3）循环（2）操作得到最后的结果。

    public int findMaximumXOR(int[] nums) {
        int ans = 0, mask = 0;
        for (int i = 31; i >= 0; i--) {

            Set<Integer> pres = new HashSet<>();
            mask |= (1 << i);
            // 获取nums所有数的第i位前缀
            for (int num: nums) {
                pres.add(num & mask);
            }

            int temp = ans|(1 << i);
            for (int pre: pres) {
                if (pres.contains(temp ^ pre)){
                    ans = temp;
                    break;
                }
            }
        }

        return ans;
    }

---

找出所有⼦集的异或总和再求和

1. leet code:https://leetcode.cn/problems/sum-of-all-subset-xor-totals/submissions/590697647/
2. 暴力解法：【可以通过】

思路：求出所有子集，然后计算每个集合的异或值，全部加起来即可。
（1）通过递归方式生成所有子集。每个元素有两种选择：要么在子集中，要么不在子集中。

    public void generateSubsets(int[] nums, int index, List<Integer> current,List<List<Integer>> subset) {
        if (index == nums.length) {
            subset.add(new ArrayList<>(current));
            return;
        }
        // 当前index不加到子集
        generateSubsets(nums, index + 1, current, subset);
        // 当前index加到子集
        current.add(nums[index]);
        generateSubsets(nums,index + 1,current,subset);
        // 撤销选择
        current.remove(current.size() - 1);
    }

    public int subsetXORSum(int[] nums) {
        // 1. 求出子集
        List<List<Integer>> list = new ArrayList<>();
        generateSubsets(nums,0, new ArrayList<Integer>(), list);

        int sum = 0;
        for (int i = 0; i < list.size(); i++) {
            List<Integer> subset = list.get(i);
            int total = subset.isEmpty()? 0 : subset.get(0);
            for (int j = 1; j < subset.size(); j++) {
                total ^= subset.get(j);
            }
            sum += total;
        }


        return sum;

    }

（2）采用位运算计算子集
思路：
对于一个数组的子集组合，每个位置上，要么有（1），要么没有（0），那么子集就可以采用位置二进制编码表示从000...～1111...，即从0～2^n-1。

   public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int len = (1 << nums.length)-1;
        for (int i = 0; i <= len; i++) {
            List<Integer> sub = new ArrayList<>();
            for (int j = 0; j < nums.length; j++) {
                // 检测第j位是否为1
                int temp = (1 << j);
                if ((temp & i) != 0){
                    sub.add(nums[j]);
                }
            }
            res.add(sub);
        }

        return res;
    }

3. 更好的解法：

   public int subsetXORSum(int[] nums) {
        int totalXOR = 0;
        for (int num : nums) {
            totalXOR |= num; // 逐位统计贡献
        }
        int n = nums.length;
        return totalXOR * (1 << (n - 1)); // 每个数字对异或的总贡献
    }

---