XOR equation with multiplication arrangment

Question

How can I move all the X to one side so the equation will become x=y XOR <somthing>... $$\begin{align} &2x \oplus y = x \end{align}$$

x and y are bytes 0-255

2x can't overflow x<127

Thanks

Answer 1

I will assume we are dealing with unsigned integers in binary representation or an boolean algebra which behave like that. i.e. algebra whose elements can be viewed as a sequence of binary digits and multiplication by $2$ corresponds to a shift of the binary digits to the right. i.e.

$$z = (z_0, z_1, z_2, \ldots )\quad\implies\quad 2z = ( 0, z_0, z_1, \ldots )$$

Notice $2x \oplus y = x \iff y = x \oplus 2x$, we have $$\begin{align}y \oplus 2y &= (( x \oplus 2x ) \oplus 2(x \oplus 2x)) = (( x \oplus 2x ) \oplus (2x \oplus 4x))\\ &= ((( x \oplus 2x ) \oplus 2x ) \oplus 4x ) = (( x \oplus ( 2x \oplus 2x ) ) \oplus 4x )\\ &= (( x \oplus 0 ) \oplus 4x ) = x \oplus 4x\\ \end{align} $$ This in turn implies $$ \begin{align} ( y \oplus 2y ) \oplus 4y &= y \oplus (2y \oplus 4y ) = y \oplus 2(y \oplus 2y)\\ &= y \oplus 2(x \oplus 4x) = y \oplus (2x \oplus 8x)\\ &= ( y \oplus 2x ) \oplus 8x = x \oplus 8x \end{align} $$ If we repeat this sort of argument, we find in general

$$\mathop{\large\oplus}_{k=0}^n 2^k y \stackrel{def}{=} ((\cdots (( y \oplus 2y ) \oplus 4y ) \cdots ) \oplus 2^n y) = x \oplus 2^{n+1} x$$

If the boolean algebra allow only finitely many digits. i.e. there is a $N$ such that $2^{N+1} z = 0$ for all $z$, then $x$ has following expression in terms of $y$:

$$x = \mathop{\large\oplus}_{k=0}^\infty 2^k y = \mathop{\large\oplus}_{k=0}^{N} 2^k y$$

Update

If we are dealing with $8$-bit unsigned integers, we can take $N = 7$ and $$x = y \oplus 2y \oplus 2^2y \oplus 2^3 y \oplus 2^4 y \oplus 2^5 y \oplus 2^6 y \oplus 2^7 y$$

In some programming like $C$, we can compute $x$ more effectively using constructs below

t  = y; 
t ^= t << 1;
t ^= t << 2;
t ^= t << 4;
x  = t & 0xff;