Solving Binary Equation

2.3k Views Asked by At

$$x = (a*y) >> 16$$

$$b = (x+7) \& ~7$$

All integers are 32 bit long; Here a is known integer >= 0; '>>' is right-shift bitwise operator which is shifted 16 times to the right; b is known integer >= 0; '*' is an integer multiplication operation; '+' is an integer addition operation; '&' is bitwise AND operator; '~' is bitwise negation operator;

How can I get the value of $x$ and $y$?

1

There are 1 best solutions below

0
On

Start by working backwards from $b$. You can see there will only be eight possible values for $b$. For each $b$, there will be $2^{29}$ values of $x$. For instance, $b = 3$, $x$ can be $4, 12, 20, 28, 36, ...$ This is arrived at by multiplying by powers of two. In binary:
$$ 000100 \\ 001100 \\ 010100 \\ 011100 \\ 100100 \\ ... $$

Now actually, you only need to consider values of $x$ up to $2^{16}$. This is due to working backwards into the first equation. By shifting 16 places left you will truncate the higher 16 bits. That brings the total number of $x$ to consider down to $2^{13}$.

Finding $y$ is a bit more awkward. Hopefully $a$ is large. For each $x$, there will be a number of $y$ that will satisfy the equation. First off, find how many $y$ there might be. Divide $2^{16}$ by $a$ (integer division; i.e. floor); call this number $k$. So for each $x$, there can be $k$ possible $y$. Find your lower $y$:

$$ y_{min} = \frac{x}{a} + 1$$ (integer division; i.e. floor).

The max $y$ is given by:

$$ y_{max} = y_{min} + k - 1 $$

For example, let $a=457$; then $k = 143$. For $y = 21798$, gives $x = 9961472$ (from the original provided equation to solve). For $y = 21940$ also gives $x = 9961472$. So any $y$ between would also work.

This works out to $$ \frac{2^{16}}{a} * 2^{13} $$ possible $x,y$ solutions for each $a,b$. Hopefully there are other criteria to narrow down valid choices.