ВКОШП: 2014/15

Соня — одиннадцатиклассница, и в этом году ей надо сдавать единый государственный экзамен по информатике. Она решила начать готовиться заранее и стала решать задачи из вариантов прошлых лет.

В многих заданиях требуется перевести число из одной системы счисления в другую. Соня с легкостью справляется с такими заданиями, но недавно в одном из вариантов ей попалась задача, которая показалась довольно интересной: число \(x\), заданное в десятичной системе счисления, требуется перевести в (−2)-ичную систему счисления.

Формально, записью числа в (−2)-ичной системе счисления называется набор чисел \(a_0, a_1, \dots , a_{n−1}\), каждое из которых равно 0 или 1, причем \(n\) = 1 или \(a_{n−1} \ne 0\) и выполнено равенство:

\(\)x = \sum\limits_{i=0}^{n-1} a_i\cdot (-2)^i\(\)

Например, 3 в (−2)-ичной системе счисления представляется набором (1, 1, 1): действительно, \(1 · (−2)^0 + 1 · (−2)^1 + 1 · (−2)^2 = 1 − 2 + 4 = 3\).

В задаче предлагается перевести в (−2)-ичную систему счисления только одно число, но Соне стало интересно решение этой задачи в общем случае.

После долгих раздумий она обратилась к вам за помощью. Помогите ей перевести заданное число в (−2)-ичную систему счисления.