minimum sum required to make xor of some integers to zero

Question

Here's a question which deals with algorithm and bitwise xor operation. We are given x1*x2*x3*....*xn=P, where star(*) operation represents XOR(bitwise) operation and x1 to xn are positive integers. P is also a positive integer. We need to find min(a1+a2+a3+.....an) such that this relation holds--> (x1+a1)*(x2+a2)*(x3+a3)*....*(xn+an)=0. '+' represents normal addition operation.

Answer 1

Restatement as a Bounded Integer Linear Programming Problem

The problem can be restated as the following bounded ILP (integer linear programming) problem.

Let x1,...,xN be as in the original problem, i.e. the goal is to minimize(a1+...+aN)
under the conditions (x1+a1) XOR ... (xN+aN) = 0, a1,...,aN >= 0.

The following is than an equivalent bounded ILP:
Find b[k,i] (0 <= k <= K, 1 <= i <= N) and s[k] (0 <= k <= K) such that
  (A) b[k,i] in {0, 1} for all i=1..n, k=0..K,
  (B) s[k] is an integer >= 0 for all k=0..K,
  (C) sum(b[k,i]*2^k, k=0..K) >= x[i] for all i = 1..N,
  (D) sum(b[k,i], i=1..N) = 2*s[k] for all k = 0..K
and minimize
  sum(b[k,i]*2^k, i=1..n, k=0..K).

From a solution of the bounded ILP the ai's are obtained by
  a[i] = sum(b[k,i]*2^k, k=0..(K-1)) - x[i]

b[k,i] is simply the k-th bit of the binary representation of (xi+ai) here (Conditions (A) and (C)). To make the overall XOR zero, an even number of b[k,i] must be 1 for every k. This is represented by conditions (B) and (D). (Note that the left-hand sum in (D) must be even if it's equal to 2*s[k] and s[k] is an integer).

K, i.e. the number of bits (plus one, actually) needed to represent all the (xi+ai) must to be determined beforehand. Picking a K such that all xi are < 2^K should suffice, i.e. the ai's are most one bit larger than the largest xi. But picking a larger K doesn't matter, the top bits will simply come out as zero. If K is picked to small, the ILP will have no solution.

Existance of a Solution

Ignoring the minimality condition, the problem can be restated as

Given x, y z with x <= y, find a and b such that (x+a) XOR (y+b) = z

Given an instance of your original problem, with N >= 2. Let x=x1, y=x2, z=(x3 XOR x4 XOR ... xn). If you find suitable a and b, set a1=a, a2=b, a3=...=an=0 to obtain a solution of the original problem.

The simplified problem is solved (again, ignoring minimality) by

1. If (y XOR z) >= x then a: = ((y XOR z) - x), b := 0 is a solution (*)
2. If (x XOR z) >= y then a := 0, b := ((x XOR z) - y) is a solution (*)
3. Otherwise, pick an a such that (x+a) XOR z >= y. Such an a always exists, you can for example let a := 2^k with 2^k > max(x,y,z). Setting b := ((x+a) XOR z) - y) yields a solution (*)

(*) To see that those really are solutions, you just need to applied a bit of algebra. For example, in case (1), after substituting a and b, you get: (x+(y XOR z)-x) XOR (y+0). Which is identical to: (y XOR z) XOR y, and thus to: z. q.e.d. Case (2) works similarly. In case (3) you get: (x+a) XOR (y+((x+a) XOR z)-y) = (x+a) XOR ((x+a) XOR z) = z.

This shows that for N >= 2, a solution always exists.

Whether or not those solutions are minimal, I do not know. In case (3), it quite obviously depends on the choice of a, so at the very least you'd have to figure out the optimal choice for a. It might also be that the original problem allows for smaller solutions than the simplified problem. Anway, maybe this restatement helps someone to figure out the complete solution.

BTW, the fact that the original problems essentially leaves you total freedom of how to "spread out" the correction values ai over the xi makes me wonder if this isn't equivalent to some sort of knapsack problem. If it is, finding a minimal solution might very well be NP-hard.

Observations regarding minimality

Take the following problem

(1+a1) XOR (3+a2) XOR (6+a3) = 0

In binary, that is

(001b+a1) XOR (011b+a2) XOR (110b+a3) = 0

The residue for a1=a2=a3=0 is 001b XOR 011b XOR 110b = 100b. An obvious solution is thus a1=4,a2=0,a3=0. Or alternatively a1=0,a2=4,a3=0. This solution is not minimal though - the following solution is smaller

a1=1, a2=1, a3=0

It's also minimal, since all smaller solutions can only have one non-zero ai, and all of the terms (2 XOR 3 XOR 6), (1 XOR 4 XOR 6), (1 XOR 3 XOR 7) are non-zero.

This shows that no gree algorithm which works from the bottom (i.e. lowest bit) upwards can work, since such an algorithm would skip the first two bits, since their residue is zero initially.

It also shows that you cannot pick a certain non-zero bit k from the residue and attempt to zero it by adding 2^k to one of the xi's. You sometimes have to add it to multiple xi's to find the minimal solution.

This pushes me a bit further towards believing that find a minimal solution is a comparatively hard problem.

Answer 2

Maybe a first inroad to the minimum - N>1, all a(i) positive - is along the following lines. Let me first state some terminology.

Initialize y(i) = x(i); y(i) stands for (x(i)+a(i)), so we initialize in fact a(i)=0 (for i=1..N). Likewise, define Q = y(1)^y(2)^...^y(N) (^ stands for XOR); initially Q=P.

We will adjust the y(i) to make Q zero, always preserving y(i)>=x(i) - i.e.: a(i)>=0.

Consider for each number (x,y,a,P,Q) its binary (bit-)expansion, numbering the bits by m=0,1,2,..: bit m represents the 2**m value-part in the number.

Note that a bit is non-zero in Q if and only if the number of y(i) that have the same bit non-zero is odd.

Proceed as follows. Scan the offending bits (value 1) in Q, top-down, i.e.: starting with the highest ('currently remaining') bit that is 1. Let this be bit #m.

We have two cases:

Case A. There is at least one y(i) that has a zero in bit m. Define C as the collection of all such y(i).

We're gonna pick one of those (see below) and set its m-bit to 1, i.e. changing

 y(i) = y(i)+(2**m). For the moment, just define INCREMENT=(2**m).

To determine our pick y(i) in collection C, we try to partially compensate the INCREMENT (2**m) by a DECREMENT as large as possible:

Iterate over the bits m-1, m-2, ... until we have a bit #n where (1.) Q has a 1 (i.e.: another offending bit that we wish to remove), and (2.) at least one of the y(i) in C also has a 1.

If this succeeds, then (1.) set:

INCREMENT = INCREMENT - 2**n (note that this remains positive);

(2.) reduce the collection C to keep only those y(i) that have bit #n non-zero; and (3.) repeat the process, scanning the bits yet further down.

As soon as we can't proceed any further, pick arbitrarily one of the remaining y(i) from C and increase it by INCREMENT. Update Q. This removes the bits {m,n,...} from Q by adding

 (2**m - 2**n - ...)

to the chosen y(i), settings its bit #m to 1 (it was 0), and its bits n,... to 0 (these were 1).

Case B. None of the y(i) has a zero in bit #m. In this case:

Iterate over bits k=m+1, m+2, ... until at least TWO y(i) have a zero in that bit. Define C1 as the collection of all such y(i), and make a copy to collection C2. Also define

INCREMENT1 as (2**k - 2**m) and set INCREMENT2 = 2**k.

Process {C1, INCREMENT1} as we did in Case A.

Remove the final pick y(i) from collection C2. Then process {C2, INCREMENT2} likewise.

Repeat all this until all bits in Q are zero.

I have not made an attempt at proving that this procedure yields the true minimum, but I do believe that this approach might be a good starting point for thinking about (the structure of) such a proof.

Answer 3

Referring to my comment - with a question not answered yet:

1. negative ai seem to be necessary: for the case N=1, a1=-x1 is the solution to the problem. I assume therefore that negative ai are allowed also in the general case.

2. Then, for N=2, there is no solution ("min") at all, apart from the fact the there is a limit to what (negative) numbers can be represented in the computer:

For N=2 set: a1=x2+K and a2=x1+K. This yields:

(x1+x2+K) XOR (x2+x1+K) = 0, irrespective of K

The sum (a1 + a2) = (x1 + x2 + 2*K)

There is no minimum solution: we can make K ever more negative.

Likewise for N>2: For N even, make pair-wise "solutions" as for N=2 (with arbitrary K's); for N odd, single one out - treat it as for N=1 - and the remaining N-1 are handled as for even N.

In all cases you construct ZERO XOR ZERO XOR ZERO ... = ZERO, where ZERO is always a pair of the type (am = xm+1 + K; am+1 = xm + K), except when N is odd, where you have one other factor, i.e. of the type {am = -xm). Except for N=1, the solutions can become as large-negative as you like.