Однажды после знакомства с
двоичной системой счисления Вася подумал, а может ли система счисления иметь
отрицательное основание. Например, минус два? Оказалось, что такая
нега-двоичная система действительно существует, и любое число записывается в
ней единственным образом.
Например, число 9 в
нега-двоичной системе записывается как 11001. Действительно, если двигаться по
его разрядам справа налево, то каждый следующий разряд соответствует следующей
степени числа −2 (то есть 1, −2, 4, −8, 16, −32 и так
далее). Единица в i-м разряде говорит о том, что соответствующая степень
добавляется к результату, а ноль − что не добавляется. В нашем примере
записи 11001 соответствует следующая сумма степеней минус двойки: 1 + (−8)
+ 16. Значение этой суммы как раз равно 9.
Всё, что требуется
от вас в данной задаче, это написать программу, переводящую натуральное число
из десятичной системы в нега-двоичную.
Входные данные
Одно целое число в интервале от 1 до 106.
Выходные данные
Запись числа
в нега-двоичной системе счисления без ведущих нулей.
|
Пример ввода 1
9
Пример вывода 1
11001
|
Пример ввода 2
6
Пример вывода 2
11010
|
