Exploring the xorspace

MATL, 11 bytes

t"G!Z~Ghu]n

Try it online!

The last test case doesn't run in the online interpreter because of memory limitations, but runs offline in less than 2 seconds on a modern computer.

Explanation

For input of size n, this does the following:

1. Initiallize result to input.
2. Repeat n times:
   1. Apply bitwise XOR to all pair of entries from current result and input.
   2. Attach input values to the result.
   3. Deduplicate.
3. The output is the number of elements of the final result.

Commented code.

t      % Implicit input: row vector. Duplicate
"      % For each (i.e. do as many times as the input size)
  G!   %   Push input as a column vector
  Z~   %   Bitwise XOR with broadcast, i.e. for all pairs of entries of the
       %   two arguments. The first argument is the accumulated result
       %   from the previous iteration, the second is the input vector
  G    %   Push input again
  h    %   Postpend
  u    %   Unique values. Gives a row vector
]      % End
n      % Number of entries. Implicitly display

Example

The intermediate results (steps 2.1 and 2.3) for input [256 259 3] are:

First iteration: [256 259 3] with [256 259 3]: computing all pairs of bitwise-XOR gives the matrix

  0   3 259
  3   0 256
259 256   0

Attaching [256 259 3] and deduplicating

0 3 259 256

Second iteration: current result [0 3 259 256] with [256 259 3]. After deduplicating this again gives

0 3 259 256

Third iteration: again

0 3 259 256

So the output is 4 (number of entries of result).

Haskell, 64 bytes

f takes a list of integers and returns an integer.

import Data.Bits
f l|m<-maximum l,m>0=2*f(min<*>xor m<$>l)|0<1=1

Try it online!

This doesn't handle an empty list, for that you can but $0: instead of the space after maximum.

How it works

• If the maximum m of the list is zero, returns 1.
• Otherwise, xors every element with the maximum.
  • If the result is smaller than the element, the element is replaced by it.
  • This necessarily zeroes the most significant bit set anywhere in the list.
  • Then recurses on the resulting list, doubling the result of the recursion.
• This process essentially performs Gaussian elimination (although throwing away the final rows by setting them to 0) modulo 2, on the matrix whose rows are the bit representations of the list of numbers. The set of bit representations of the "xorspace" is the vector space modulo 2 spanned by the rows of this matrix, and whose number of elements is 2 to the power of the matrix's row rank.
• This algorithm is polynomial time, so should definitely be better than O(2^n).

Mathematica, 52 bytes

2^MatrixRank[PadLeft@IntegerDigits[#,2],Modulus->2]&