进制转换 之 商和余数 [AtCoder-4239] Base -2 Number 负二进制数

https://vjudge.net/problem/AtCoder-4239

水题。

关于进制转换，就相当于以怎样的基数（余数）来看待一个数字。

题目大致是让我们将一个整数（-1e9~1e9）转化为负二进制数，并且由01串组成。

在表达的时候是不会出现-1搭配的情况的如（-3）不是（-1-1），而是1101，而我们计算n对（-2）取余的时候是会出现-1的，因此我们要把这个-1变成正1。举个例子，对于-5转化为负二进制，第一步为 -5= （-2 ）*2（2为商）+（-1），我们要把最后这个（-1）变为1，那么只有改变商，即-5=（-2）*（2+1）+1。此时就得到了我们要的1 .

那么在处理的时候，就在标准的迭代中增加一个，如果余数为-1，不符合表达要求，就改为余数为1，而本身的值减2，使得经过处理的数再进入下一次的转换。

注意特判0。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5;

int n;
int dig[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    int cnt=0;
    if(n==0){
        cout<<0<<endl;
        return 0;
    }
    while(n){
    //    cout<<n%(-2)<<endl;
        if(n%(-2)==-1){
            dig[++cnt] = 1;
            n-=2; 
        }
        else{
            dig[++cnt] = (n%(-2));
        }
        n/=(-2);
    //    cout<<"n="<<n<<endl;
    }
    for(int i=cnt; i>=1; i--){
        cout<<dig[i];
    }
}