Exploring the xorspace

Question

The xorspace of a set of integers is the set of all integers that can be obtained by combining the starting integers with the usual bitwise xor operator (^). For example, the xorspace of (8, 4) is (0, 4, 8, 12): 0 is 4^4, 12 is 4^8, and no other numbers can be reached. Note that the starting numbers are always included, by this definition (for example, 4 is 4^4^4).

Your goal is to write the shortest program that takes a list of non-negative integers as input, and outputs the number of elements in their xorspace.

• Standard loopholes are forbidden.
• Input and output can be in any of the usual formats. Input is guaranteed to be valid, non-empty, and without duplicates.
• Your code should be able to process all test cases in less than a day.

Test cases

Input: 0
Output: 1

Input: 6
Output: 2

Input: 8 4
Ouput: 4

Input: 0 256
Output: 2

Input: 256 259 3
Output: 4

Input: 60 62 94 101 115
Output: 32

Input: 60 62 94 101 115 40 91
Output: 32

Input: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
Output: 64

Input: 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384
Output: 32768

Answer 1

Pyth, 8 bytes

lu{+xM*Q

Test suite

Explanation:

To generate the xorspace, we find the fixpoint of taking the xor of every pair of numbers, adding in every number, and deduplicating. Then, we take the length of the result. This runs in 20 seconds (offline only) on the final test case.

lu{+xM*Q
lu{+xM*QGGQ    Implicit variable introduction
 u        Q    Find the fixed point of the following, starting with the input,
               where the current value is G.
      *QG      Form the Cartesian product of Q (input) and G (current)
    xM         Take the xor of every pair
   +           Add the current values
  {            Deduplicate
l              Output the length of the result.

---

Packed Pyth, 7 bytes

Hexdump:

0000000: d9d7 dabf 1355 51                        .....UQ

The same as the above, with a 7-bit ASCII encoding.

Put the above in a file with xxd -r, and run it as follows:

py packed-pyth.py xorspace.ppyth '[256, 259, 3]'

Answer 2

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).

Answer 3

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).

Answer 4

Mathematica, 52 bytes

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

Answer 5

05AB1E, 8 bytes

vDy^ìÙ}g

Try it online!

All test-cases finish in under 1 minute on TIO.

Answer 6

Python 2, 55 bytes

r={0}
for n in input():r|={x^n for x in r}
print len(r)

Try it online!

Beats out functions:

f=lambda l,r={0}:l and f(l[1:],r|{x^l[0]for x in r})or len(r)
f=lambda l:len(reduce(lambda r,n:r|{x^n for x in r},l,{0}))

---

Ørjan Johansen's beautiful row elimination method is one byte shorter.

Python 2, 54 bytes

f=lambda l:1-any(l)or 2*f([min(x,x^max(l))for x in l])

Try it online!

Answer 7

Jelly, 9 8 bytes

0œ|⁺^¥/L

Finishes all test cases in under 8 seconds on TIO, with negligible memory requirements.

Try it online!

How it works

0œ|⁺^¥/L  Main link. Argument: A (array)

0œ|       Perform multiset union with 0, prepending 0 if A doesn't contain it.
      /   Reduce A by the link to the left.
     ¥      Combine the previous two links into a dyadic chain.
            Left argument: V (array). Right argument: n (integer)
    ^           Bitwise XOR each element in V with n.
   ⁺            This quick refers to the previous link, making it a shorthand for
                the link 'œ|'. Thus, it performs multiset union on V and the array
                of bitwise XORs.
       L  Compute the length of the result.

Answer 8

Python, 113 bytes

def f(x):
 u,s=[0],{0}
 while u:
	a=u.pop()
	for b in x:
	 c=a^b
	 if c not in s:u+=[c]
	 s.add(c)
 return len(s)