Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
    
Similar post on cs.SE. –  Raphael Jul 4 '12 at 8:49

1 Answer 1

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.