Hashing astut? P78794

Abans de plantejar aquest problema, us recordem (o informem) que:

Donats dos enters @a@ i @b@, en C++ (@a@^@b@) és el XOR d’@a@ i @b@. És a dir, n’és el “or exclusiu bit a bit”: el resultat d’operar cada parell de bits és 1 sii els dos bits són diferents. Per exemple, (9^12) $=$ ($1001_2$^$1100_2$) $= 0101_2 =$ 5.

Donats dos enters @x@ i @n@, en C++ (@x@<<@n@) és el resultat de desplaçar @x@ @n@ bits cap a l’esquerra. Si no hi ha sobreiximents, dóna el resultat de multiplicar @x@ per 2 elevat a @n@. Per exemple, (9<<2) $=$ ($1001_2$<<2)$= 100100_2 =$ 36.

Ara, el problema. L’Edgar ha descobert un nou algorisme de hashing al qual li veu un gran futur en aplicacions criptogràfiques. Semblant a tants altres métodes, combina moltes operacions de bits, per la qual cosa podria ser complicat recuperar la informació original.

L’Edgar ha decidit que treballarà amb enters de $B = 30$ bits (és a dir, módul $2^B$). Donats dos enters $a$ i $b$, defineix:

L’Edgar ens assegura (i té raó) que donats $a$ i $c = h(a, b)$, només hi ha una $b$ possible. Ell creu que el seu mètode és prou segur, és a dir, que no es pot obtenir $b$ eficientment a partir d’$a$ i de $c$. Demostreu que l’Edgar és un palomo.

Entrada

L’entrada consisteix en diversos casos, cadascun amb $a$ i $c$, dos enters entre 0 i $2^{30} - 1$.

Sortida

Per a cada cas, escriviu la $b$ corresponent.