We’re rewarding the question askers & reputations are being recalculated! Read more.

# Tag Info

4

Suppose that your numbers are $n$-bit long. Then you can think of them as elements of the vector space $\mathbb{F}_2^n$. The number $X$ can be written as an XOR of $a_1,\ldots,a_m$ if $X$ is in the linear span of $a_1,\ldots,a_m$. In order to determine whether $X$ is in the linear span of $a_1,\ldots,a_m$, you can use Gaussian elimination.

3

No. $a\oplus b = c$ and $c\oplus b = a$ are just rearrangements of the same equation, since $$a\oplus b = c \iff (a\oplus b)\oplus b = c\oplus b\iff a=c\oplus b\,.$$

2

For every $i \in \{0,\ldots,n\}$ (where $n$ is the length of the array) and for every $a,b,c \in \{0,\ldots,15\}$, we determine whether it is possible to partition the first $i$ elements of the array into four subsets, the first three of which XOR to $a,b,c$, respectively. We also compute the XOR of the entire array. Using the information for $i = n$, we can ...

1

Yes, there are ways to improve the efficiency greatly. Let ${}_k{i}$ be the $k$-th digit of $i$ in binary representation, i.e., it is 0 if $\lfloor i/2^k\rfloor$ is even and 1 otherwise. For example, since $19=(10011)_2$, $_019=1$, $_119=1$, $_219=0$, $_319=0$, $_419=1$. In most programming languages, ${}_k{i}$ can be computed as $(i\text{>>}k)\%2$. ...

1

Introducing another integer variable $t$, you can express the condition $x_1 \oplus x_2 \oplus \cdots \oplus x_n = 1$ as in the following canonical form. $$x_1 + x_2 + \dots + x_n - 2t \le 1$$ $$- x_1 - x_2 - \dots - x_n + 2t \le -1$$ $$(x_1, x_2, \cdots, x_n) \le (1,1,\cdots,1)$$ $$(x_1, x_2, \cdots, x_n, t) \ge \mathbf 0$$ (x_1, x_2, \cdots, x_n, t) \in \...

Only top voted, non community-wiki answers of a minimum length are eligible