题意分析

给定一个十进制整数 $N$（$-2 \times 10^9 \leq N \leq 2 \times 10^9$），要求将其转换为基数为 $-2$ 的表示形式。基数为 $-2$ 的数字系统位值如下（从右到左）：

即第 $k$ 位的权值为 $(-2)^k$。

解题思路

要将十进制数 $N$ 转换为基数为 $-2$ 的表示，可以采用短除法，但需要注意以下几点：

1. 余数必须为 $0$ 或 $1$（因为二进制表示只含 $0$ 和 $1$）。
2. 基数 $-2$ 导致除法规则不同：
   • 当 $N$ 除以 $-2$ 时，商和余数的计算方式需要调整：
     • 如果 $N$ 是偶数，直接计算 $N / (-2)$，余数为 $0$。
     • 如果 $N$ 是奇数，余数必须为 $1$，因此商计算为 $(N - 1) / (-2)$。
3. 重复直到商为 $0$，然后将余数倒序排列即可得到结果。

标程

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    
    if (n == 0) {
        cout << "0\n";
        return 0;
    }
    
    vector<int> digits;
    int tmp;
    
    while (n != 0) {
        tmp = n % 2;
        if (n < 0) tmp = -tmp;
        digits.push_back(tmp);
        n = (n - tmp) / (-2);
    }
    
    for (int i = digits.size() - 1; i >= 0; --i) {
        cout << digits[i];
    }
    cout << '\n';
    
    return 0;
}