Hi mike:

There is a thread in the newbie forum that may fall in your area of expertise

http://www.woodmann.net/forum/showthread.php?s=&threadid=3990

It boils down to solving for x the following equation

x + a = x xor b xor c

where a, b, c are known and x is unknown. We could replace b xor c = d
being d another known quantity
giving:

x + a = x xor d

Does this equation have an analytical solution?

I am not sure, but if we could express

x + a

in terms of logic operations, xor, and, not, even if they are valid only in a finite numeric space, or conversely, express

x xor d

in terms of an algebraic formula the equation could be solvable.


Is it possible?


Thanks for your comments

There's an infinite number of solutions if there are any. Try solving it for small numbers and you'll see what I mean.

Essentially, any place that a and d don't match you have a carry:

0+1 =1
0^1 =1

1+1=10
1^1=00

so you just have to keep track of the carry bit as you move from low order bits to high order bits.

It should be obvious that there's no solution if a and d are opposite parity, i.e. one is odd and the other is even.

Also, since XORing can never set carry bits, there are no solutions if a>d

Also, d has to be of the form (2^n)(2^m - 1) because every time you carry, there's another 1 in d, and no more bits are affected when the carrying stops. For instance:
011101 + 001000 = 100101 = 011101 ^ 111000
111000 = (2^3)(2^3-1)

So there are no solutions if d is not of the form (2^n)(2^m - 1)