How could I open parentheses which have an addition inside and a bitwise xor outside?

Asked Jun 23 '21 at 16:02

Active Jun 23 '21 at 18:04

Viewed 81 times

I have a system of equations:

$$ \left\{ \begin{array}{c} y - x = c \\ y \oplus x = d \end{array} \right. $$

$x, y$ - positive (32bit) integer variables, which I want to find.

$c, d$ - integer constants.

$\oplus$ - bitwise xor.

I can make a first step by showing that $y = c + x$ and so $(c+x) \oplus x = d$. How could I find the $x$ from the last equation?

I was able to come up with one more step. By applying the xor $x$ to both sides we get $c+x = d \oplus x$.

If there are any $c$ and $d$ for which it is impossible to solve the system, then you may just not consider such $c$ and $d$.

edited Jun 23 '21 at 18:04

asked Jun 23 '21 at 16:02

qqqqqqq

What domain are you working with? – copper.hat Jun 23 '21 at 16:02
@copper.hat, just playing around with leetcode. If you are interested in details here is the problem. In the referenced problem I am able to find the $c$ and $d$ in linear time and constant space. So, I am left with tackling the $x$ and $y$. :) – qqqqqqq Jun 23 '21 at 16:04
I don't understand what space you are in. Presumably something like $\mathbb{B}^n$ in which case is subtraction twos complement? – copper.hat Jun 23 '21 at 16:12
$x$ and $y$ are just usual variables of $int$ type. – qqqqqqq Jun 23 '21 at 16:12
Your system will not (necessarily) have unique solutions. – paw88789 Jun 23 '21 at 16:22
You have $x=y \oplus d$. – copper.hat Jun 23 '21 at 16:23
@paw88789, I updated my question a bit. – qqqqqqq Jun 23 '21 at 16:23
You might want to elaborate that you are working with finite bit size. – copper.hat Jun 23 '21 at 16:35
@copper.hat, done. – qqqqqqq Jun 23 '21 at 16:36
There may not be a solution, for example if $c=1 1 \cdots 1, d = 0$ then there are no $x,y$ satisfying the equation. – copper.hat Jun 23 '21 at 17:42
@copper.hat, let me update my question. :) – qqqqqqq Jun 23 '21 at 18:03

0 Answers0