Efficient method to get one number, which can't be generated from any XORing combination

Question

If there is any number in the range [0 .. 2⁶⁴] which can not be generated by any XOR composition of one or more numbers from a given set, is there a efficient method which prints at least one of the unreachable numbers, or terminates with the information, that there are no unreachable numbers? Does this problem have a name? Is it similar to another problem or do you have any idea, how to solve it?

Answer 1

Each number can be treated as a vector in the vector space (Z/2)^64 over Z/2. You basically want to know if the vectors given span the whole space, and if not, to produce one not spanned (except that the span always includes the zero vector – you'll have to special case this if you really want one or more). This can be accomplished via Gaussian elimination.

Over this particular vector space, Gaussian elimination is pretty simple. Start with an empty set for the basis. Do the following until there are no more numbers. (1) Throw away all of the numbers that are zero. (2) Scan the lowest bits set of the remaining numbers (lowest bit for x is x & ~(x - 1)) and choose one with the lowest order bit set. (3) Put it in the basis. (4) Update all of the other numbers with that same bit set by XORing it with the new basis element. No remaining number has this bit or any lower order bit set, so we terminate after 64 iterations.

At the end, if there are 64 elements, then the subspace is everything. Otherwise, we went fewer than 64 iterations and skipped a bit: the number with only this bit on is not spanned.

To special-case zero: zero is an option if and only if we never throw away a number (i.e., the input vectors are independent).

---

Example over 4-bit numbers

Start with 0110, 0011, 1001, 1010. Choose 0011 because it has the ones bit set. Basis is now {0011}. Other vectors are {0110, 1010, 1010}; note that the first 1010 = 1001 XOR 0011.

Choose 0110 because it has the twos bit set. Basis is now {0011, 0110}. Other vectors are {1100, 1100}.

Choose 1100. Basis is now {0011, 0110, 1100}. Other vectors are {0000}.

Throw away 0000. We're done. We skipped the high order bit, so 1000 is not in the span.