Solution: Sum of All Subset XOR Totals

Statement

Given an array of integers, nums, compute and return the sum of XOR totals for all its possible subsets.

• A subset is any combination of elements from the original array, nums. This includes the empty subset (containing no elements) and the subset that includes all array elements.

• The XOR total of a subset results from applying the XOR operation to all the elements in that subset.

Note: If the nums array has duplicate elements, then subsets that contain the same elements but with different indexes are treated as separate. Each subset’s XOR total is counted in the final sum.

Constraints:

• $1 \leq$ nums.length $\leq12$

• $1 \leq$ nums[i] $\leq 20$

Solution

A naive approach to solving the problem would involve generating all possible subsets, calculating the XOR for each, and summing the results. However, with up to $2^n$ subsets for an array of length $n$, this method becomes impractical due to its exponential growth.

To overcome this inefficiency, we use bitwise operations to determine how each number in the array contributes to the XOR total without generating all subsets. We can achieve this by using the properties of subset generation, binary numbers, and bitwise manipulation. The solution can be divided into two main parts:

• Bitwise OR: XOR affects bits set to $1$, so use bitwise OR to find each number’s contribution toward the XOR total. It identifies set ($1$) bits across the array.

• The sum of XOR totals: Left-shift the OR result (binary form) by ($n-1$) positions for the contribution of bits across all subsets (sum of XOR totals). Alternatively, we can multiply the decimal value of the result by $2^{n–1}$. This is because each number in an array appears in exactly half of the possible subsets, which is $2^{n–1}$.

XORXOR is a binary operation that returns 1 when the bits of the operands are different and 0 when they are the same. is a bitwise operator, so instead of focusing on the whole numbers, we'll focus on their binary bits. For XOR, the only bits that matter are the ones that are set to 1 (set bits). These bits can flip the XOR result at that position from 0 to 1 and vice versa. Therefore, it’s important to figure out which positions in the binary representation of the numbers have 1s. For this, we can use the bitwise OR operation. It processes an array by taking the first two numbers, performing OR on them, then taking this result and the next number to perform OR on them, and so on. This process continues for all $n$ numbers, accumulating all set bits across the array in the final result.

Once we know which bits are set, we don’t need to explicitly compute the XOR for each subset. We know these active bits will affect the XOR total, and we can calculate their combined effect directly. For this, we multiply the OR result by $2^{(n-1)}$. This is because each bit will participate in exactly halfsumOfXOR of the subsets, and thus, its contribution to the XOR total can be scaled by the number of times it appears across all subsets. If we have to perform this step concerning bitwise manipulation, we'll left shift the result by $n-1$ positions.

Let's look at the algorithm steps given below:

• Initialize a variable output to $0$. This variable will store the cumulative OR result of all numbers in the array.

• Iterate over the array, and for each number num, perform a bitwise OR operation between output and num. Update output with the result. This step collects all bits that could potentially influence the XOR of any subset.

• After processing all the numbers, left shift (<<) the output by (len(nums) - 1) bits, and return the output. Alternatively, we can multiply the output with $2^{len(nums)-1}$ to get the final value.

The slides below help to understand the solution in a better way.