 PDA

View Full Version : Call for Mike's comments

naides
October 16th, 2002, 22:31
Hi mike:

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

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?

mike
October 18th, 2002, 05:14
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.

mike
October 21st, 2002, 21:34
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)