Maximization with xor operator

Let the "length" of a number be the number of digits needed to write it out in binary, excluding any leading zeros. Equivalently, the length of a number is the position of the leading $1$ bit in its binary representation.

Clearly, if all the input numbers had a different length, the problem would have a trivial solution: just iterate over the input numbers in decreasing order by length, choosing each number if and only if XORing it with the maximum so far increases the maximum, i.e. if and only if its leading bit is not set in the current maximum.

Since this is an algorithmic question, let me provide some pseudo-code to illustrate the algorithm I just described:

# Find maximum XOR of input, assuming that all input numbers have
# different length:

let max = 0
for each number n in input (sorted in descending order by length):
    if max < (max XOR n): let max = (max XOR n)

(To see why this algorithm works, first observe that each bit in a binary number is "worth" more than all the lower bits combined, so we clearly want to work from top down, first optimizing the highest bits, no matter what this does to the lower bits.

Now assume that we've already considered all the input number longer than $k$ bits, and determined the maximum value the bits higher than $k$ can have in their XOR, and that we're now considering whether to XOR a $k$-bit number — which, by assumption above, is the only $k$-bit number in the input — into the maximum or not. We cannot change the bits above the $k$-th bit by doing so, but we can always ensure that the $k$-th bit in the result is set, by XORing the current input number into the result if and only if the $k$-th bit of the result so far is not yet set. Further, ensuring that the $k$-th bit is set is clearly more important that anything that may happen to the lower bits as a side effect, so we may ignore those bits for now.)

The tricky part is when the input may contain multiple numbers with the same length, since then it's not obvious which of them we should choose to include in the XOR. What we'd like to do is reduce the input list into an equivalent form that doesn't contain more than one number of the same length.

Conveniently, this is exactly what Gaussian elimination does: it transforms a list of vectors into another list of vectors which have strictly decreasing length, as defined above (that is, into a list which is in echelon form), but which still spans the same linear subspace.

The reason this linear algebra algorithm is relevant here is that binary numbers satisfy the axioms of a vector space over the finite field of two elements, a.k.a. GF(2), with the numbers viewed as vectors of bits, and with XOR as the vector addition operation. (We also need a scalar multiplication operation to satisfy the axioms, but that's trivial, since the only scalars in GF(2) are $1$ and $0$.)

The linear subspace spanned by a set of bit vectors (i.e. binary numbers) over GF(2) is then simply the set of vectors obtainable by XORing a subset of them. Thus, if we can use Gaussian elimination to convert our input list into another one, which spans the same subspace, we can solve the problem using this other list and know that it gives the same solution as for the original problem.

Thus, we need to implement Gaussian elimination over GF(2). Fortunately, this turns out to be very simple (in fact, much simpler than doing it for ordinary vectors of real numbers):

1. Find the maximum length $k$ of the (remaining) inputs, and at least one input having that length. Set this input aside.

2. XOR all other inputs of length $k$ with the input set aside in step 1: their length will now become less than $k$.

3. Repeat from step 1, until all remaining inputs have length $0$ (and can therefore be discarded).

4. The inputs set aside during successive iterations of step 1 above will form the new input list. (Conveniently, they will already be in decreasing order by length.)

A useful optimization is to separate the inputs into a number of "buckets" (i.e. variable-length lists) by their length: this makes finding the maximum length, and all inputs having that length, very easy and efficient.

Here's some pseudo-code again:

# Preliminary phase: split numbers into buckets by length
for each number x in input:
    let k = length of x
    if k > 0: add x to bucket k

# Gaussian elimination:
for each bucket (in decreasing order by k):
    if this bucket is empty: skip rest of loop
    let x = arbitrary (e.g. first) number in this bucket
    remove x from this bucket
    add x to modified input list

    for each remaining number y in this bucket:
        remove y from this bucket
        let z = y XOR x
        let k = length of z
        if k > 0: add z to bucket k

Then just apply the maximum-finding algorithm given above to the modified input list.

(Ps. It's also possible to find the subset of input numbers giving the maximum XOR using this algorithm: for each modified input number, you just need to somehow keep track of which original input numbers it was XORed from. This is basically the same algorithm as using Gaussian elimination to find a matrix inverse, just adapted to bit vectors.)

The Gaussian elimination in this case will work as follows.

First sort the numbers in a non-ascending order. Now visualize the binary representations of all the numbers in a matrix. Consider them to be non-negative 64 bit integers. (Note: you don't have to actually convert them to binary or make the matrix, use bit operations on an array of numbers)

Then carry out the "Forward Elimination" phase of Gaussian Elimination. First find the MSB position (i.e. the first 1) of the very first number. Make sure that all the numbers below it don't have have a '1' at this position. If they do then just XOR them with the number at top and their bits at this position will become zero. After that move on to the next row and next column, and repeat the process. If at anytime you find that the row you are working on does not have a 1 at the desired position, then carry out "Pivoting". Look for any number below that may have a 1 at this position and swap the rows i.e. the numbers. If all numbers below also have 0's then stay at the same row and move on to the next column, and keep repeating the process if all you find are 0's. (For this problem you don't have to be at the last row and last column at the same time.)

Once elimination is done simply traverse each row of the matrix. Have a variable called result which is initially 0. You have to take the first row since it has the highest MSB. By taking I mean carrying out XOR operation with your current result variable. Then move on to the next row and column. If you see that your result has a 0 at this column then XOR with the number at this row since it can only increase your sum or keep it the same. In this way check all the rows, and the result you finally have is the maximum xor sum. (An easier way to think of this would be that you only XOR a row with your current result if it increases the current result.)

What we are doing here is trying to make each number 1 bit shorter than the previous number. This makes it easier for us to think of the XOR operations without thinking of how it may effect the bits to the left. You may have to think a little to understand why this solution is valid.