Conceptual bitmasking & power sets

I was recently working my way through this problem Sum of All Subset XOR Totals and found a valuable use case for bitmasking. While backtracking is naturally the faster solution for this problem, (an interesting topic for another day) we will be exploring how we can use the traits of a series of binary values to generate all possible subsets, i.e. the power set.

If you’ve ever needed to generate all possible subsets of a collection, this is a core technique you’ll want to understand. It’s an elegant and efficient way to handle combinatorial problems. Let’s dive into how it works.

The Problem

First, a quick look at the problem. You’re given an array of integers, nums. The goal is to find every possible subset of nums, calculate the XOR total for each subset, and then find the sum of all those totals.

For instance, with the array [1, 3], the subsets are:

• [] (the empty set) -> XOR total is 0
• [1] -> XOR total is 1
• [3] -> XOR total is 3
• [1, 3] -> XOR total is 1 ^ 3 = 2

The final answer is the sum of these totals: 0 + 1 + 3 + 2 = 6.

The main challenge is generating these subsets efficiently. A bitmasking approach provides a clear and direct path.

Application

Here’s the Java solution that utilizes bitmasking:

class Solution {
    public int subsetXORSum(int[] nums) {

        int sum = 0;
        int n = nums.length;

        // The number of possible subsets is 2^n - 1.
        // We can represent this with a left shift: 1 << n == 2^n.
        // The loop will iterate from 0 to (2^n - 1), representing each possible subset.
        for (int i = 0; i < (1 << n); i++) {

            // We can initialize as 0 because 0 xor n yeilds n
            int xorSum = 0;
            // Now, we build the subset corresponding to the mask 'i' and compute the xorsum.
            for (int j = 0; j < n; j++) {

                // Check if the j-th bit is set in our mask 'i'.
                // If it is, the number at nums[j] is in the current subset.
                if ((i & (1 << j)) != 0) {
                    xorSum ^= nums[j];
                }
            }
            sum += xorSum;
        }

        return sum;
    }
}

The foundational idea is that for a set with n elements, there are exactly $2^n$ possible subsets. We can map every integer from 0 to $2^n - 1$ to a unique subset. How? By using the binary representation of the integer as a “mask.”

Each bit in the binary number corresponds to an element in our original array. If the bit is a 1, we include the corresponding element in our subset. If it’s a 0, we don’t.

Let’s use [1, 3] again. Here, n = 2, so we have $2^2 = 4$ subsets. We will loop from i = 0 to 3, and use the binary representation of i as our mask:

This is exacty what the code implements.

1. The Outer Loop: for (int i = 0; i < (1 << n); i++) is the engine of our subset generation. 1 << n is a concise way to write $2^n$. The loop variable i serves as our decimal counter, which is our bitmask.

2. The Inner Loop & The Bitwise Check: Inside, the inner loop iterates through our original numbers. The key line is if ((i & (1 << j)) != 0).

• 1 << j creates a value where only the j-th bit is 1 (e.g., 0001, 0010, 0100…).
• The & (bitwise AND) operator compares our mask i with this value. If the j-th bit is also set in i, the result of the AND operation will be non-zero.
• When this condition is true, it confirms that the element nums[j] belongs to the current subset, and we include it in our xorSum.

After the inner loop completes, we have the xorSum for one subset. We add it to the total sum and move to the next mask.

On duplicates and sets

In this LeetCode problem, duplicates in the input array are treated as distinct for the purpose of creating subsets. For example, if the input was [5, 5], the subsets would be [], [5], [5], and [5, 5]. The bitmasking approach naturally handles this, as it considers positions (nums[0], nums[1]), not values.

In other problems, you might need only unique subsets. In that case, you could use a Set data structure to store the subsets you generate, as a Set automatically filters out any duplicates.

Wrapping up

So, that’s bitmasking in action. A very systematic approach to solving problems involving power sets and combinations. Understanding how to represent subsets with binary masks is a valuable skill that will be useful to add to your arsenal.

Happy coding!