12

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.

5
  • Are xi positive integers, or can they also be negative?
    – IVlad
    Sep 29, 2012 at 19:08
  • @IVlad All integers are positive.
    – halkujabra
    Sep 29, 2012 at 19:11
  • I think more details are needed. What are the limits on ai? Must they also be positive? How large can they be?
    – IVlad
    Sep 29, 2012 at 19:33
  • @IVlad All integers are non-negative! So, also all ai's are >=0
    – halkujabra
    Oct 2, 2012 at 6:39
  • @user1708762 Did you manage to solve the problem, under the minimality condition?
    – mayank
    Jan 7, 2013 at 17:45

3 Answers 3

4

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.

2
  • All integers are non-negative! So, also all ai's are >=0
    – halkujabra
    Oct 2, 2012 at 6:40
  • @user1708762 yup, I figured that. My answer only produces ai's >= 0. Otherwise, it's trivial to see that a solution always exists, just set ai = -xi.
    – fgp
    Oct 2, 2012 at 9:28
1

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.

9
  • Hm, so for even N, there is a solution
    – fgp
    Sep 30, 2012 at 7:15
  • In a sense, yes, you're right of course (and that also applies to odd N>2, adjusting the K's to push the negative sum to the limit that is representable), but I assume that this is not the type of solution the asker was looking for... Sep 30, 2012 at 7:20
  • Hm, so for even N, a solution always exists, even if the a[i] are required to be positive. The question thus becomes (for even N only!) whether a[i] = x[1]+...+x[i-1]+x[i]+...+x[n] is the minimal solution. For N=1 I agree that there is no solution with a1 >= 0, unless you allow overflow to occur. I'm not convinced, however, that the same is true for N >1, N odd. Who says you can't find an odd number of integers yi with yi >= xi and y1*...*yn = 0?
    – fgp
    Sep 30, 2012 at 7:23
  • I just realized that a[i] = x[1]+...+x[i-1]+x[i]+...+x[n] is definitely not the minimal solution for odd N. Making two adjacent pairs of (x[i]+a[i]) cancel each other out, i.e. a[i] = {x[i-1] if i is odd, x[i+1] if i is even}, will generally produce a smaller solution. For even N, x0+...+xn is thus a bound for a0+...+an.
    – fgp
    Sep 30, 2012 at 7:32
  • 1
    For N even, imposing the requirement of positive ai, you get a lower minimum than your general {a(i)=sum(all x(j))-x(i)}, by pairing, along the lines in my answer. A first shot would be to sort the x(i), then pairwise set {a(i)=(x(j)-(x(i)); a(j)=0}. The result is the sum of the pairwise differences (x(j)-(x(i)). Btw, I believe we should also await a response from the person who asked the question, to clarify what is required/allowed. Sep 30, 2012 at 7:33
1

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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