At first I asked this question on Stackoverflow, where I was advised to ask here. So there is the question:
I have a system of pretty simple equations:
\begin{align} x + y &= A \\ f(x,y) + y &= B \end{align}
$A$ and $B$ are known. All of variables are 64 bit positive integers, including $f(x,y)$.
But the problem is that $f(x,y)$ uses bitwise operations: $$ f(x,y) = x \oplus (x << 3) \oplus y \oplus (y >> 14) $$ where $\oplus$ denotes XOR, and $<<$ and $>>$ denote the left- and right-bit shifts, respectively.
I tried to solve this by representing arithmetic addition with bitwise opperations and carry-bits. I also tried to represent each bit as a boolean value and then solve a system of boolean equations. I didn't succeed any much. So is there any method of doing this properly?
This is by no means an answer, but too long for a comment.
A first idea:
Maybe do Krylov subspace method on two binary vectors $\bf x,y$. Define $f$ to be the operation that bit-wisely does whatever it does, treat it as a matrix multiplication inside the algorithm. Then the scalar value for $x$ and $y$ is given by scalar product with these binary vectors: $x = [2^{63},2^{62},\cdots,1] {\bf x}$ and analogously for $y, \bf y$.
I have not done Krylov subspace methods in practice on non-floating point arithmetics, so I cannot promise it will work.
Some more general observations.
We can by checking the sign of:
$B-A= f(x,y) -x$
$B-2A= f(x,y) -y- 2x$
$B-4A= f(x,y) -3y- 4x$
$B-8A= f(x,y) -7y- 8x$
Estimate the size relation between $x$ and $y$.
Furthermore $x+y=A$ will be bigger than the biggest of $x,y$, but smaller than the biggest of $2x$ and $2y$. Those are $y<<1$ and $x<<1$
$x \oplus (x<<3)$ will mark the magnitude of $x$ with the highest set bit. The two following bits will also be unmodified x bits. The complication here is of course if $y$ is orders of magnitude larger than $x$ then it will start corrupting these bits when $\oplus y$ part comes into play.