4
$\begingroup$

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

  • 0
    [Similar post on cs.SE](http://cs.stackexchange.com/q/2590/98).2012-07-04

1 Answers 1

6

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

  • 0
    It feels natural to start with the most significant $b$it, where there is some XOR-discrepancy. If for no other reason than $b$ecause 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?2012-06-29