Solving a system of equations using both arithmetic and bitwise operations 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:


$x + y = A$
$f(x,y) + y = B$


$A, B$ are known. All of the 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 \ll 3) \oplus y \oplus (y \gg 14)$$

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?
So is there any method of doing this properly?


Here's the most obvious method:


Iterate through the lower 14 bits of $y$, that is, you'll perform the below steps for each of the 16384 possible settings of the lower bits of $y$
Compute what the lower 14 bits of $x$ are, using $x = A - y$ (because the subtraction is modulo $2^{64}$, we can ignore everything higher than bit 13)
Compute what the next 14 bits of $y$ must be, using $y &gt;&gt; 14 = (B - y) \oplus x \oplus (x &lt;&lt; 3) \oplus y$
Compute what the next 14 bits of $x$ are, using $x = A - y$ (only this time, because we know 28 bits of $y$, we can reconstruct 28 bits of $x$)
Compute what the next 28 bits of $y$ must be...
Keep on doing this until we start predicting bits of $y$ above 63; because the right shift shifts in 0's, the prediction must be that they are all 0 (and if it predicts something else, we can reject the original guess of the lower 14 bits of $y$).


This involves iterating through 16384 different possibilities; a tad tedious by hand, but fairly trivial for a computer program...

I threw together a quick C routine to do the above search:

typedef unsigned long long num;
void solve_it(num a, num b) {
unsigned lower_14_y;

for (lower_14_y = 0; lower_14_y &lt; (1&lt;&lt;14); lower_14_y++) {
    num y, x, upper_y = 0;
    int i;

    for (i=1;; i++) {
        y = (upper_y &lt;&lt; 14) + lower_14_y;
        /* Lower i*14 bits of y are accurate */
        x = a - y;
        /* Lower i*14 bits of x are accurate */

        if (14*i &gt;= 64) break;  /* Got all the bits */
        upper_y = (b - y) ^ x ^ (x &lt;&lt; 3) ^ y;
    }

    if (b != y + (x ^ (x &lt;&lt; 3) ^ y ^ (y&gt;&gt;14))) {
        continue;
    }
    printf( "Found solution %llx, %llx\n", x, y );
}
}


On my machine, it takes 80usec to run, and as kelalaka suspected, sometimes there aren't any solutions, and sometimes there are multiple (e.g. for a = 0x6c, b = 0xee, there are 7 solutions)