# algorithm related to XOR

I have $N$ values, $a_1,a_2,a_3\ldots a_N$. Now let us say i could increase any of these values by any amount such that the XOR sum becomes zero.

$$(a_1+d_1) \oplus (a_2+d_2) \oplus \cdots \oplus (a_n+d_n) =0$$

i need to find the deltas $d_1,d_2,d_3,\ldots,d_n$ such that the sum of deltas is minimized. any delta , $d_k \ge 0$.

$N$ could be up to $100$ in my case.

Could you please tell if there is any known way to compute it.

Many thanks

-
Sounds hard. Wouldn't surprise me if it was NP-complete. – Henning Makholm Jun 28 '12 at 17:57
Which of your signs are plus and which are XOR? If + is plus, you better allow dn to be less than zero or you will never get there. – Ross Millikan Jun 28 '12 at 18:01
(+) is xor sign – JCH Jun 28 '12 at 18:09
– Raphael Jul 4 '12 at 8:49

I don't have an optimal solution, but here's at least a quick and dirty algorithm to generate what might be a "good enough" solution, at least for even $n$. But first, let me reformulate the problem a bit:

Given the non-negative numbers $a_1, a_2, \dotsc, a_n$, we wish to find numbers $b_1, b_2, \dotsc, b_n$ such that $a_i \le b_i$ for all $i \in \{1, 2, \dotsc, n\}$, $b_1 \oplus b_2 \oplus \dotsb \oplus b_n = 0$ and the sum $b_1 + b_2 + \dotsb + b_n$ is minimized. (We can then let $d_i = b_i - a_i$ to obtain a solution to the original problem.)

Now, here's an approximate algorithm to obtain such $b_i$:

1. We start by letting $b_i = a_i$ for all $i \in \{1, 2, \dotsc, n\}$ and calculating $c = b_1 \oplus b_2 \oplus \dotsb \oplus b_n$.

2. If $c = 0$, we're done. Otherwise, let $k$ be index of the highest bit in $c$, i.e. the largest integer such that $2^k \le c$. (Equivalently, $k = \lfloor \log_2 c \rfloor$.)

3. We will now look for the smallest increment to some $b_i$ that will flip the $k$-th bit in that $b_i$ — and thus in $c$ — and no higher bits. To do that, let $\beta_i = b_i \bmod 2^k$ and choose $j \in \{1, 2, \dotsc, n\}$ so as to maximize $\beta_j$, subject to the condition that the $k$-th bit of $b_j$ is 0 (i.e. that $b_j \bmod 2^{k+1} < 2^k$). As long as $n$ is even, we're guaranteed to find at least one such $b_j$.

4. Then replace $b_j$ with $b_j + (2^k - \beta_j)$, recalculate $c$ using the new value of $b_j$, and repeat from step 2.

The proof that this algorithm must terminate, for even $n$, follows from the fact that $c$ must decrease on every iteration. However, this proof only works for even $n$, as for odd $n$ it's possible that the $k$-th bit of $b_i$ is 1 for all $i \in \{1, 2, \dotsc, n\}$ in step 3. In that case, incrementing any $b_i$ so as to flip its $k$-th bit will also flip (at least) the $k+1$-th bit, which will increase $c$.

It's not hard to see that this algorithm in fact does generate the optimal result $b_1 = b_2 = \max(a_1, a_2)$ for the trivial case $n = 2$. I don't know whether it's optimal for any higher $n$, but I doubt it. However, at least it's fairly fast and won't produce absurdly large solutions. (In fact, it guarantees that $d_1 + d_2 + \dotsb + d_n \le a_1 \oplus a_2 \oplus \dotsb \oplus a_n$.)

-
Actually, I think I have a better algorithm that starts with the lowest bit of $c$ rather than the highest, but I still need to prove that it always terminates. – Ilmari Karonen Jun 28 '12 at 22:43
Correction: I originally claimed that the number of iterations needed was bounded by the Hamming weight of $a_1 \oplus a_2 \oplus \dotsb \oplus a_n$, but that's clearly not true: a simple counterexample is e.g. $a_1 = 1$, $a_2 = 16$, $a_3 = a_4 = 15$. – Ilmari Karonen Jun 29 '12 at 20:48
It feels natural to start with the most significant bit, where there is some XOR-discrepancy. If for no other reason than because that is the bit you would concentrate on when proving that a NIM-game has a move leaving a position with XOR-sum zero. Here the objective is different, so it may be the wrong way? – Jyrki Lahtonen Jun 29 '12 at 21:20