Solving XOR equation: X ^ Y = X - Y

The given equation to be solved in the integral domain is the following:

X ^ Y = X - Y, where X >= 0, Y >= 0 ................... (1)

• As always, we have X ^ Y >= 0, we are restricted to values, X >= Y as the set of all solutions should be constrained to. This implies,

For all (x, y) satisfying the eqn. (1), we have, X >= Y.
The solution lies below and/or on the line Y = X in the First quadrant.

• Next step would be to figure out the boundaries. We have,

o  For X = 0, Y = 0
o  For X = Y, (1) is satisfied. 
o  For Y = 0, (1) is satisfied.

Hence, any (t, t) or (t, 0) where X >= t >= 0, is a valid solution.

• Curiously, we have (0, 0) (X, X) and (X, 0) forming the elements of solution. Hence, we could shape out a triangle forming out of it. Stopping hereby, we would like to explore further. We would like to find the value of ‘X’, say ‘K’ (X = K) for which we have ‘Y’ takes all values, K >= Y >= 0 as solution.

Let X = K. And let Y = { 0, 1, ..., K } be the values of Y when X takes K. Then, we have

K ^ Y = K - Y, where K remains a constant. 

Consider, K = <a_n  a_n-1  a_n-2 ... a_3  a_2  a_1> be the binary representation where a_r = {0, 1}.
Lets say, Y = <b_n  b_n-1  b_n-2 ... b_3  b_2  b_1> where b_r = {0, 1}.

We know, if we perform 'K - Y', and lets say, if b_r > a_r and a_r+1 = b_r+1 then, 
as a rule of subtraction, we would have a_r = a_r + 10 (base 2) and we have a_r+1 != b_r+1.
This would result in a contradiction since the XOR would return "01" for whereas subtraction
would return "11". 

If a_r+1 != b_r+1, and b_r > a_r, even in this case, we would have, a_r+1 = b_r+1 after the
borrow operation and that would affect a_r+2 or any other bits further thus disturbing the XOR.

• This clearly shows that we should have a_r >= b_r for all n >= r >= 1. Hence, we have

K = 111...111, (in Base 2) or in short, K = Pow(2, n)-1
Hence, if K = Pow(2, n)-1 then, we have Y = { 0, 1, ..., K } as solutions.

• This increases the curiosity rather. We have for every X = Pow(2, t)-1, we’ll have a vertical line correspoding to Y values till it reaches X.

• Finding the above result very curious, we tend to look up for other special values of K for which the equation would hold. Here we have K as,

 Letting K = Pow(2, m) * (Pow(2, n)-1) 
 We have K = 11..(n-times)..100..(m-times)..0
 
 From the XOR operation and the "-" operation above we could easily deduce that:
 o  We should have Y >= Pow(2, m).
 o  Also, Y | Pow(2, m).
 
 This provides a much more clarity about the number of solutions that is:
 Y = { 0, Pow(2, m), 2*Pow(2, m), 3*Pow(2, m), ..., (Pow(2, n)-1)*Pow(2, m) }
 But the number of solutions of Y has not changed. Moreover, each solution is separated 
 by Pow(2, m). 

Hence we find amidst of pillars, another kind of pillars that are highly disconnected.

• Now the actual solution strikes as a flash. We’ll have to go back and reconsider the representation of X and Y and review the operations of XOR. We have following results.

Letting X = <a_n  a_n-1  ....  a_2  a_1> and Y = <b_n  b_n-1  .... b_2  b_1>
We have, for XOR,
            a_n  a_n-1  a_n-2  ....  a_3  a_2  a_1
            b_n  b_n-1  b_n-2  ....  b_3  b_2  b_1

Lets say, some N bits of X are 1's and others are 0's. We must then have, the corresponding 
bits of Y aligned with the 1-bits of X to have either 1 or 0 value. Since from our above 
observation, we cannot have a_r < b_r, we have only Pow(2, N) possible places to fill 1's and 0's
for forming Y. 

Hence for a given X, the Y can have Pow(2, N) values, where N = Number of 1's in X.

• This completes the actual puzzle. Now that we have the number of solution for a given X, we try to sum it up all along the line. Before closing down this puzzle, we would like to recollect a few things up from the elementary combinatorics.

Given a L-bit number, number of such numbers having exactly r 1's in their representations 
is expressed simply as C(L, r) where C(n, r) is the standard function nCr.
                                                     ....................... (2)

Also, Pow(1 + t, n) = SUM[ C(n, r)Pow(t, r) ] Where,  n >= r >= 0.
                                                     ....................... (3)

• The final piece of the puzzle of what the equation when plotted on the graph would be like is here:

The total number of solutions when considering X to take values in {0, 1, ..., Pow(2, n)} 
is given by, 

     Number of solutions = Pow(3, n)   (Isnt it surprising?)

Here is how: We have number of values of X having 1 1's is C(n, 1) and that the number of 
solutions for the corresponding one is given by Pow(2, 1). Similarly, considering number of
values of X having r 1's is C(n, r) and that the number of solutions is Pow(2, r). 

Summing up using the identities (2) and (3), we get, Pow(1 + 2, n) = Pow(3, n) as the result.

The above number of solution points arouse the deep suspicion over the shape actually the solution takes when plotted over the X-Y plane. It has got to represent a Sierpinsky Gasket over a Right-Triangle.

The confirmation is got through the plot of solutions, X taking values over [0, 256).

Finally, one of the problem solved. But another one still remains, the basic question of what is the behaviour of the bit-wise operators in arrangement of numbers?

NOTE An interesting property this XOR operator has is that in a set of L-bit binary strings, they form an Abelian group under this operation!