Introduction

The maximum XOR over all subsets of an array is a classic problem where brute force looks tempting but fails quickly. An array of length n has 2^n subsets, so direct enumeration becomes impractical almost immediately. The standard efficient solution builds a linear basis over bits, which is essentially Gaussian elimination for XOR arithmetic.

Why XOR Basis Works

XOR behaves like binary addition without carries. That means numbers can be treated as vectors over bits, and we can reduce the input array into a smaller set of independent values called a basis.

The important property is this: once the basis is built, every XOR value you could make from the original array can still be made from the basis, but the basis is much smaller and easier to reason about.

For typical integers, the basis size is at most the number of bit positions, not the number of subsets.

Build the Basis from High Bits to Low Bits

The usual algorithm picks a pivot value for each bit, starting from the highest bit and working downward. Then it clears that bit from all other basis candidates.

1def max_subset_xor(arr):
2    values = arr[:]
3    row = 0
4    n = len(values)
5
6    for bit in range(63, -1, -1):
7        pivot = row
8        while pivot < n and ((values[pivot] >> bit) & 1) == 0:
9            pivot += 1
10
11        if pivot == n:
12            continue
13
14        values[row], values[pivot] = values[pivot], values[row]
15
16        for i in range(n):
17            if i != row and ((values[i] >> bit) & 1):
18                values[i] ^= values[row]
19
20        row += 1
21
22    answer = 0
23    for value in values:
24        answer = max(answer, answer ^ value)
25
26    return answer
27
28
29print(max_subset_xor([2, 4, 5]))  # 7

This runs in roughly O(n * B), where B is the number of bits. That is dramatically better than O(2^n).

Small Example

Consider [2, 4, 5].

Binary forms:

• '2 = 010'
• '4 = 100'
• '5 = 101'

Possible subset XOR values are:

• '0'
• '2'
• '4'
• '5'
• '2 ^ 4 = 6'
• '2 ^ 5 = 7'
• '4 ^ 5 = 1'
• '2 ^ 4 ^ 5 = 3'

The maximum is 7. The basis method finds that answer without listing subsets one by one because it keeps only the independent bit contributions that matter for the maximum.

Why the Final Greedy Step Is Correct

After elimination, the basis is arranged so that each pivot contributes a distinct highest bit. To maximize the final number, start from zero and try applying each basis value. If answer ^ value is larger than answer, keep it.

That greedy rule works because higher bits dominate lower bits numerically. Once the basis is reduced, taking a value either improves the most significant reachable prefix or it does not.

C++ Implementation

This is a common competitive-programming pattern, so here is the same idea in C++:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5using namespace std;
6
7long long maxSubsetXor(vector<long long> a) {
8    int row = 0;
9    int n = static_cast<int>(a.size());
10
11    for (int bit = 63; bit >= 0; --bit) {
12        int pivot = row;
13        while (pivot < n && (((a[pivot] >> bit) & 1LL) == 0)) {
14            ++pivot;
15        }
16
17        if (pivot == n) continue;
18
19        swap(a[row], a[pivot]);
20
21        for (int i = 0; i < n; ++i) {
22            if (i != row && ((a[i] >> bit) & 1LL)) {
23                a[i] ^= a[row];
24            }
25        }
26
27        ++row;
28    }
29
30    long long answer = 0;
31    for (long long x : a) {
32        answer = max(answer, answer ^ x);
33    }
34    return answer;
35}

Using long long makes the implementation safer for larger inputs than a 32-bit int.

Common Pitfalls

One common mistake is confusing this problem with the maximum XOR of any pair. That is a different problem and often uses a trie instead of a linear basis.

Another mistake is hardcoding the bit range too narrowly. If the array can contain large integers, a 31-bit loop may silently miss the best answer.

Developers also sometimes build the elimination step correctly but forget the final greedy reconstruction. The reduced basis alone is not the answer until you maximize over it.

Finally, brute force may seem acceptable for tiny arrays, but it does not scale. The linear-basis method is the standard solution for a reason.

Summary

• Maximum subset XOR is solved efficiently with a bitwise linear basis.
• The basis preserves every reachable XOR value from the original array.
• Build pivots from high bits to low bits, then greedily maximize the result.
• The algorithm runs in roughly O(n * B) instead of O(2^n).
• This is the standard approach for subset-XOR optimization problems.