算法
(进制转换) $O(\log N)$
1 0 1 1
-8 4 -2 1
(-8)+(-2)+1=-9
N -> ?
10进制 -2进制
初始:[0, 0]
1 -2 4 -8 16
+ 选 [1, 1] [-2, -1] [2, 5] [-10, -3]
不选 [0, 0] [0, 1] [-2, 1] [-2, 5]
[0, 1] [-2, 1] [-2, 5] [-10, 5] [-10, 21]
虽然这里是负进制数,但依然可以使用除 $-2$ 取余倒计法,但 C++ 中的整数除法和取模是向 $0$ 取整的,比如 $\lfloor \frac{-9}{-2} \rfloor = 4$,但实际上应该是 $5$,$-9 \% -2 = -1$ 但实际上应该是 $1$。
具体做法:
若 $n$ 不能被 $2$ 整除,则将 $n$ 减 $1$,并在答案左边添加 $1$,否则在答案左边添加 $0$,然后将 $n$ 除以 $-2$,一直持续这个操作直到 $n$ 变成 $0$ 时停止。
C++ 代码
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::string;
int main() {
int n;
cin >> n;
string ans = "";
while (n != 0) {
if (n % 2 != 0) {
n--;
ans = "1" + ans;
}
else ans = "0" + ans;
n /= -2;
}
if (ans == "") ans = "0";
cout << ans << '\n';
return 0;
}