文件读写

• 输入文件base.in
• 输出文件base.out

限制

• 1000ms
• 512MB

题目描述

程老师整理旧物时翻到一台上古计算机的说明书，里面记载了一种奇怪的计数法——负二进制。

负二进制和二进制很像：从右往左第 $i$ 位（从 $0$ 开始数）依然是 $0$ 或 $1$，但它表示的数值是 $(-2)^i$，而不是 $2^i$。

说明书还给出了把十进制整数 $n$ 转成负二进制的方法：不断除以 $-2$ 取余数，余数依次就是负二进制从右往左的每一位。但有一条修正规则：余数必须是非负的（$0$ 或 $1$），如果某一步算出负余数，就把商加 $1$、余数加 $2$ 再继续。

特别地，$n = 0$ 时输出 0；输出的最高位不能是 $0$（$n = 0$ 本身除外）。

程老师想考考大家：给定一个十进制整数 $n$（可能是正数、负数或 $0$），它的负二进制表示是什么？

输入格式

一行一个整数 $n$。

输出格式

一行一个 $01$ 字符串，$n$ 的负二进制表示。

数据范围

特殊性质 A：$n$ 为正整数。

特殊性质 B：$n$ 为负整数。

1

1

-3

1101

7

11011

样例解释

样例2：按修正规则逐位计算——

余数从右往左依次是 $1, 0, 1, 1$，即 1101。验证：$(-2)^3 + (-2)^2 + (-2)^0 = -8 + 4 + 1 = -3$。