非常感謝你閱讀本文~
歡迎【👍點贊】【?收藏】【📝評論】~
放棄不難，但堅持一定很酷~
希望我們大家都能每天進步一點點~
本文由 二當家的白帽子 https://le-yi.blog.csdn.net/ 博客原創~

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

分析

1. 直接按照題意照做

• 窮舉所有可能的子集，O(2ⁿ)的時間復雜度，慢了，但是能做出來至少說明基礎良好吧，不過這是演算法題，討厭了，得優化，

2. 找到內在規律

• 這題欺負數學不好的同學，沒關系，二當家的想辦法不用專業數學知識去解釋，
• 多個數做異或操作就是看每個位上1的數量是奇數，還是偶數，0沒有貢獻（0和x異或，結果就是x，對于x相當于沒做操作），
• 從陣列里窮舉子集，每個數字只有2種選擇（選擇它和不選它），一共有2ⁿ個子集，所以每個數字被選中2^n-1次，所以每個數字中那些為1的位，也是做出2^n-1次運算貢獻哦，
• x * 2^n-1相當于x << (n - 1)，
• 別問我為什么，問就是，因為所以，科學原理，

題解

java

題目說什么，我們干什么的方式

class Solution {
    public int subsetXORSum(int[] nums) {
        int ans = 0;

        // 數字個數
        final int n    = nums.length;
        // 用每一位表示某個數字是否被選中
        final int bits = 1 << n;

        for (int b = 0; b < bits; ++b) {
            int temp = 0;
            for (int i = 0; i < n; ++i) {
                if ((b & (1 << i)) > 0) {
                    temp ^= nums[i];
                }
            }
            ans += temp;
        }

        return ans;
    }
}

利用規律的方法

class Solution {
    public int subsetXORSum(int[] nums) {
        int bits = 0;

        // 所有位上出現過1的數
        for (int num : nums) {
            bits |= num;
        }

        // 這些1乘以貢獻次數
        return bits << (nums.length - 1);
    }
}

c

int subsetXORSum(int* nums, int numsSize){
    int bits = 0;

    // 所有位上出現過1的數
    for (int i = 0; i < numsSize; ++i) {
        bits |= nums[i];
    }

    // 這些1乘以貢獻次數
    return bits << (numsSize - 1);
}

c++

class Solution {
public:
    int subsetXORSum(vector<int>& nums) {
        int bits = 0;

        // 所有位上出現過1的數
        for (auto num : nums) {
            bits |= num;
        }

        // 這些1乘以貢獻次數
        return bits << (nums.size() - 1);
    }
};

python

class Solution:
    def subsetXORSum(self, nums: List[int]) -> int:
        bits = 0
        ## 所有位上出現過1的數
        for num in nums:
            bits |= num
        ## 這些1乘以貢獻次數
        return bits << (len(nums) - 1)

go

func subsetXORSum(nums []int) int {
	bits := 0

	// 所有位上出現過1的數
	for _, n := range nums {
		bits |= n
	}

	// 這些1乘以貢獻次數
	return bits << (len(nums) - 1)
}

rust

impl Solution {
    pub fn subset_xor_sum(nums: Vec<i32>) -> i32 {
        let mut bits = 0;

        // 所有位上出現過1的數
        nums.iter().for_each(|n|{ bits |= n;});

        // 這些1乘以貢獻次數
        bits << (nums.len() - 1)
    }
}

原題傳送門