Maximization with xor operator

Question

With given N numbers only one of those numbers doesn't have pair, which one is it? After hours of surfing the net i found that XOR operator is good for that, because

X xor X=0
X xor 0=X

and

A xor B xor C = B xor A xor C

so we can do xor in any order. But yesterday i've found next nice problem. With given N numbers i have to pick subset of them which XOR is as maximum as possible. I've figured out that if we want to have maximum result we need to xor numbers with totally different(or at least similiar) binary representation, but i think it's too slow approach. How to deal with this one? Cheers

P.S.: SPOJ Problem: http://www.spoj.pl/problems/XMAX/

Answer 1

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.

Answer 2

Iterate over the bits from highest to lowest, determining for each bit its value in the result. Each bit $i$ is set in the result iff there is a subset whose XOR yields the already determined higher bits and also has bit $i$ set: if there is no such subset, it's not possible for bit $i$ to be set in the result, and if there is one, then any value in which bit $i$ is not set will be lower than the value for that subset.

Thus, the problem is reduced to finding, for each bit $i$, if possible, a subset whose XOR yields the already determined higher bits and also has bit $i$ set. But this is just a system of linear equations over $\mathbb Z_2$, the field with two elements, which can be solved using Gaussian elimination. Since the matrix of this system always has the same rows, with a new row being added for each bit, it might be possible to determine more efficiently whether the system has a solution; this is enough, except for the last bit, for which the system has to actually be solved in order to determine the solution.