Zadanie - wskazówka

Question

Dzień dobry! Mam zadanko typu

x xor 2*x = k

na wejściu mamy -> k

i naszym zadaniem jest odzyskanie X w czasie mniejszym bądź równym logarytm z k ( k jest do  2*10^9)

Jak w temacie prosiłbym o podanie wskazówki do rozwiązania zadania.

Comments

Pomoc nadal potrzebna ?

---

Tak

Answer 1

Trzeba te liczby zamienić na system dwójkowy. 2*x będzie wtedy o jeden bit dłuższa od x, ponieważ mnożenie przez 2 w systemie binarnym to przesunięcie bitowe w lewo. Czyli jak mamy dajmy na to x = 101101, to 2x = 1011010. Długość 2x w bitach będzie równa więc długości k. Aby wyrównać długość x do k dodamy nieznaczące 0 z przodu. Mamy więc coś takiego:

k = 10110101
x = 01******
2x= 1******0

Cyfry liczba oznaczona przez gwiazdki w x i 2x musi być taka sama ( no bo to przesunięcie bitowe). Skoro już to wiemy to dalej prosto: * XOR 1 = 0 czyli kolejna cyfra w 2x to 1. A skoro mamy ją w 2x to mamy też w x tylko na mniej znaczącej pozycji. Mamy więc:

k = 10110101
x = 011*****
2x= 11*****0

Krok oczywiście powtarzamy aż będzie całe x.

Comments

Dziękuję za pomoc lecz uważam to jako rozwiązanie już, a mi chodziło o wskazówkę ​​​​​ w tym momencie jedynym wyzwaniem jest to naklepac. 

---

przepraszam :(, jestem początkującym forumowiczem. Ale bardzo dziękuję za skorygowanie :)