Problem z hashowaniem liczby naturalnej

[borovsky]

Witam, otrzymałem na laboratorium zadanie napisania algorytmu hashującego, który wymaga policzenia czegoś takiego:
"o ile to możliwe, zapisać liczbę w postaci \(\displaystyle{ 2^i - 2^j}\). Algorytm musi być ten nienaiwny więc odpada "dobieranie" wykładników.
Pomożecie?

[Afish]

Mam dwie metody, zalecam drugą.
Metoda 1:

Ukryta treść:    

\(\displaystyle{ 2^i - 2^j = 2^j(2^{i-j} -1)}\)
Ponieważ nasze komputery nie przechowują zazwyczaj wielkich liczb, wystarczy tak naprawdę maksymalnie kilkadziesiąt iteracji, aby sprawdzić, czy da się liczbę przedstawić w takiej postaci. Dzielenie + logarytmy i po sprawie.

Metoda 2:

Ukryta treść:    

Wykorzystując przekształcenie z metody pierwszej, zauważmy, że jeżeli liczbę da się przedstawić jako różnicę odpowiednich potęg dwójki, to będzie ona w zapisie binarnym wyglądała tak:
\(\displaystyle{ 111 \ldots 1 00\ldots 0}\)
Czyli na początku będzie miała ileś jedynek, potem będzie miała ileś zer. Jeżeli ma inną postać, to na pewno nie da się jej przedstawić jako różnicę potęg dwójki. Teraz wystarczy tylko zauważyć, że:
\(\displaystyle{ k =\underbrace{111\ldots1}_{n}\underbrace{000\ldots0}_{m} = 2^{n + m} - 2^{m}}\)

[borovsky]

bardzo dziękuję. A tak spytam z ciekawości... Sam na to wpadłeś, jeśli tak to ile czasu Ci to zajęło. Ja miałem czas tylko na laboratorium...

[Afish]

Sam, jakieś 5-10 minut.